https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] BFS를 구현하여서 풀었는데 처음에 이 문제를 풀지 못했다. 그래서 다른 분들이 푼 코드를 보고 푸는 방식을 공부한 후에 풀었다. for문에서 x-1 , x+1, x * 2를 가는 방식을 BFS에 구현하는 것이 하나의 주의할 부분, 두번째는 N과 K가 같을때의 조건을 추가하는 것이 또 하나의 주의할 부분이라고 생각한다. 이 문제에 대해서 100퍼센트 이해하지는 ..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [풀이] 바이러스는 연결되어 있는 컴퓨터 모두에게 전파되므로 연결되어있는 모든 컴퓨터를 탐색하면서 count++를 하면 된다. DFS를 이용해서 문제를 풀었으며 DFS는 스택을 이용해서 구현했다. 주어진 입력값에 맞게 2차원 배열에 연결되어있는 부분은 1로, 그렇지 않으면 0으로 초기화를 한 후, 방문하지 않은 곳은 visited 배열에 false로, 방문한 곳은 true로 값을 수정하면서 구현했다. ..
https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net [풀이] BFS를 이용하여 문제를 풀었다. 음식물이 있는 곳은 1로 표시를 한 후, 음식물이 있는 곳에서 상하좌우로 움직이며 count변수를 더한 후, 최대값을 구했다. 문제에서 주의할 부분은 첫째, BFS를 구현할 수 있는지, 둘째, 음식물이 있는 곳을 기점으로 상하좌우를 살피므로 반복문을 통해서 count 변수의 최대값을 구하는 부분 이렇게 두가지라..
https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net [풀이] 처음에는 해당하는 길이의 문자열을 substring으로 자른 후, for문을 돌면서 일치할 경우 answer++을 하는 식으로 풀었는데 그렇게 되니 50점밖에 얻지 못했다.(서브태스크) 그래서 DP를 이용해서 "IOI"가 일치할 경우 dp의 배열에 1씩 더하며 N의 개수 이상이 될 경우 answer++하는 방식으로 풀었다..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] BFS, DFS 관련해서 공부하는 과정에서 풀어본 기본 문제이다. 기본 문제인 것같은데도... 푸는데 쉽지가 않았고 오래 걸렸다. BFS를 큐로 구현해서 풀었으며 지나가는 곳을 visited 배열과 arr 배열을 통해서 조건을 확인하며 풀어나갔다. 아무래도 BFS와 DFS 기본 문제이기에 해당 알고리즘을 잘 구현하기만 하면 풀 수 있었던 것 같다. 얼른 코테 잘해지고 싶다.. 공부하자... [코드] import java..
https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net [풀이] DFS를 이용하여 문제를 풀었다. 그래프를 돌면서 'W'일 때와 'B'일때를 구분해서 개수를 더해주는 식으로 풀이를 진행했다. 그래프 문제와 DFS를 구현할 줄 알면 크게 어렵지는 않았던 것 같다. 최근에 있었던 시험도 그렇고 항상 느끼는게 DFS와 BFS 그리고 그래프에 대해서 부족한게 많다고 느껴서 한동안은 이 부분에 집중할 생각이다. 그래서 개념도 다시 한번..
