(이코테 w/ Python) DFS & BFS 문제 풀이
문제 1. 음료수 얼려 먹기
문제 해결 아이디어
이 문제는 연결 요소 찾기(connected component) 문제이다.
DFS 혹은 BFS로 해결할 수 있으며 연결 요소 개수가 몇 개 인지 구하면 되는 문제이다.
얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링할 수 있다.
다음과 같이 3 X 3 크기의 얼음 틀이 있다고 가정해보자.
이와 같이 그래프 형태로 모델링을 해보면
상하좌우로 연결되어 있는 위치들은 서로 인접한 노드 형태로 표현할 수 있다.
특정 기점에서 DFS 혹은 BFS를 수행해서 이동 가능한 모든 경로에 대해서 방문처리를 진행할 수 있다.
(왼쪽 상단에 있는 0에서 시작된다면 인접한 0 노드 2개가 방문처리 된다)
1인 노드는 이동이 불가능한 노드로 처리한다. 그렇다면 0인 노드, 3개만 방문처리된다.
이렇게 DFS 혹은 BFS를 수행해서 방문처리가 이루어지는 지점에 대해서만 카운트 처리하여 전체 연결 요소 개수를 알아낸다.
DFS를 활용하는 알고리즘은
- 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면 연결된 모든 지점을 방문할 수 있다.
- 모든 노드에 대하여 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트한다.
답안 예시
dfs를 확인해보면
주어진 범위를 벗어나는 경우 종료될 수 있도록 하고
그렇지 않은 경우, 현재 위치를 아직 방문하지 않았다면 방문처리를 하는 것이다.
결과적으로 true 값을 반환할 수 있도록 해서 (return True)
현재 위치에 대해서 처음 dfs가 수행된 것이기 때문에
위치에 대해 result 값을 증가시킨다 (추후에)
연결된 모든 위치에 대해서 방문 처리를 진행하기 위해 상하좌우 위치에 대해서 재귀적으로 dfs를 호출한다.
상하좌우에 대해서 호출되는 내용들은 return 값을 사용하지 않기 때문에 연결된 모든 노드에 대해서 방문처리를 수행하기 위한 목적으로 수행된다.
n과 m을 입력 받고
n 줄에 걸쳐서 2차원 리스트에 맵 정보를 받는다.
이때 입력은 공백 없이 0과 1로 구성된 문자열 형태로 주어지기 때문에 한줄로 입력받은 다음에 (int, input())
각 원소를 정수형으로 바꿔서(int~) 리스트 형태로 만들어 준다.
그러면 모든 원소가 0 혹은 1인 정수 리스트가 들어간다.
n x m 각 위치에서 dfs를 수행한다.
현재 위치에 대해 dfs를 수행해서 방문처리가 된거라면 (if ~ True)
카운트가 진행되도록 한다(result += 1)
문제 2. 미로 탈출
문제 해결 아이디어
BFS를 이용한다.
BFS를 통해 간선의 비용이 모두 같을 때 최단거리를 탐색한다.
BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.
상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일하다.
따라서 (1,1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.
3X3 크기의 미로가 있다고 가정해보자.
(1, 1)의 위치에서 시작한다.
인접한 노드에서 값이 1인 노드로만 이동이 가능하다.
옆 노드를 방문하게 되면 2로 변하게 된다.
시작 위치와 마지막 위치(오른쪽 하단 1)를 포함해서 마지막 위치까지 도달하는 최단 거리 경우에 포함되는 노드의 수를 출력해야하기 때문에 한 번 이동한 거리를 2라고 표현할 수 있는 것이다.
2 또한 큐에 담기게 되고 다시 2 노드를 꺼낸 다음에 상하좌우로 연결되어 있는 노드를 확인한다.
매번 새로운 지점을 방문할 때 이전 지점까지 방문한 거리에 1을 더한 값을 기록할 수 있도록 한다.
마지막 위치에 기록되어 있는 최단 거리 값을 출력할 수 있도록 만들면 된다.
답안 예시
덱을 이용해서 큐 기능을 이용한다.
x, y 로 이루어진 큐플 데이터를 담는다.
큐가 빌 때 까지 bfs를 수행한다.
반복할 때 마다 큐에서 하나의 원소를 꺼내서 (popleft())
현재 위치에서 4가지 방향으로의 위치를 확인한다.
공간을 벗어나면 무시하고
괴물이 존재해서 이동할 수 없다면 무시하도록 한다.
결과적으로 해당 노드를 처음 방문할 때만 최단 거리를 기록할 수 있도록 한다.
...= graph[x][y] + 1직전 노드 위치에서의 최단 거리 값에 1을 더한 값을 (graph에)넣어줄 수 있도록 한다.
다음으로 이동할 위치까지는 1만큼 거리가 더 먼곳이기 때문에 이와 같이 큐에 데이터를 넣으면서 거리값을 증가시킬 수 있다.
n과 m의 값을 입력 받고,
2차원 데이터가 담길 수 있는 맵 정보를 받는다.
공백으로 구분되지 않고 0과 1로 구성된 문자열이 주어지기 때문에
단순히 문자열을 입력받고 (input())
각 원소를 정수로 바꾸어 (int)
리스트를 만드는 방법을 사용한다(list)
이렇게 그래프를 초기화한다.
방향 벡터를 정의하고
bfs 함수를 호출한다.