: BFS(넓이 우선 탐색)과 관련된 문제라서 풀어봤다.
문제 분석
: 왼쪽 최하단 좌표에서 우측 최상단 좌표로 이동하는 경우에 최단거리로 가는 거리가 얼마나 되는지를 구하는 문제이다. 0,1 로 이뤄진 좌표에서 1은 지날 수 없는 부분이고, 0만 지날 수 있다. n*m의 크기를 가졌는데, n,m 각각 1보다 같거나 크고, 천보다 작거나 같다.
문제 설계
: 일단 이 문제에서의 포인트는 특정 좌표에서 특정 좌표로 '최단거리'로 가는 케이스를 찾아내야한다는 것이다. 또한, 최단거리로 가면서 마주치는 장애물(1)을 피해가면서 가는 케이스를 잘 찾아내야한다. 즉, x에서 y로 가는 최단거리는 사실 정해져있겠지만, 그 안에 장애물들이 있기 때문에 실제로 탐색을 해봐야 알 수 있는 것이다. 그러면 최단 거리를 구하려면 어떤 해결책을 찾아야할까? 를 생각해보면, 일단 이 맵자체가 그래프 형태로 표현됨을 알아야한다. 그리고 이러한 그래프를 탐색할 때 DFS, BFS를 떠올릴 수 있어야하고, 그중에 DFS로는 이번 문제를 풀 수 없다는 걸 알아야할 것 같다. BFS로 풀어야지만, 한칸한칸 전진하면서 최단거리로 거리를 측정하며 거리를 잴 수 있다. DFS로 하면 완전히 돌아가는 길도 서슴없이(?) 탐색을 하게 될 것이다. 하나의 길이 아닌 여러개의 갈림길이 있는 길을 탐색하면서 동시에 최단거리를 찾으려면, 모든 갈림길을 한번에 한걸음씩 걸어보면서 측정하다가, 마지막에 도착지점에서 이길이 최단거리로 가는 길이구나 알 수 있는데, 그것을 가능하게 해주는 것이 BFS!
문제 풀이
- board라는 1차원 배열에 input으로 주어진 배열을 받아 넣되, 장애물과 같은 숫자인 1로 그 테두리를 경계처리 해준다.
- (n,1) 의 자식 노드부터 탐색을 시작하는데, 이 때, 각각의 거리 정보를 copy_board(board의 깊은 복사버전)에 입력하면서 탐색한다. 예를 들어, 시작 노드의 바로 아래 자식 노드들에는 1을 적어준다. 이런식으로 진행하다보면 마지막 (1,m) 인덱스를 찾았을 때 거기에 최단거리가 적힐 것이기에 그것을 답으로 출력해주면 된다.
- 그러면 각각의 거리정보를 어떻게 입력하면서 BFS를 할지 구현해보면, 먼저 root 노드의 거리정보에 0을 입력해주는데, 이 때, 거리정보는 dictionary에 입력해놓는다. 또한, 이 dictionary는 해당 좌표를 탐색했는지 여부도 알려줄 수 있게한다.
- while 문을 사용해서 탐색하는 부분을 작성하되, while 문의 조건은 len(queue) != 0, 즉, 큐의 길이가 0이되면 break걸리게 한다.
- while문 내부에는 top = queue.pop(0) 이렇게 실제 자료구조 큐처럼 맨앞에 있는(FIFO) 자료를 pop해서 그 자료를 바탕으로 그 자식노드를 얻어온다음에, 그 자식 노드들에 대해서 이 top의 거리에 +1을한 값을 dictionary에 입력해준다. 이 때, 만약 자식 노드들 중에 이미 dictionary에 있는 값이 있다면, 이미 들른 것이기에 패스한다.
- 그렇게 dictionary에 입력을 해주면서 그 자식 노드들을 모아서(방문하지 않은 자식 노드들만) queue에 합쳐주고 다음 while 문으로 넘어간다. 이렇게 계속 하다보면, 결국 모든 요소를 탐색하게 될 것이고, 그러다가 방문하지 않은 노드인데, (1,m)의 인덱스를 가졌다면, 거기서 break를 걸고, 마지막에는 copy_board[1][m]에 적혀있는 값을 리턴해준다.
코드 구현
import copy
n,m = map(int,input().split())
board = []
for i in range(n):
board.append([1]+list(map(int, input().split()))+[1])
limit_line = [[1 for i in range(m+2)]]
board = limit_line + board + limit_line
root = (n,1) # (n-1,0)이 아닌 이유는 경계처리를 해줬기 때문!
path = {} # 거리 정보를 담을 dictionary
path[root] = 0
# root의 거리정보를 담을 필요는 없지만, 이미 들른 곳이라는 것을 표시하기 위함
queue = [root]
copy_board = copy.deepcopy(board)
while len(queue) != 0:
top = queue.pop(0)
up = (top[0]-1,top[1])
right = (top[0],top[1]+1)
down = (top[0]+1,top[1])
left = (top[0],top[1]-1)
next_arr = []
for el in [up,right,down,left] :
prev_len = path[top]
if copy_board[el[0]][el[1]] != 0 :
continue
else:
copy_board[el[0]][el[1]] = prev_len + 1
path[el] = prev_len + 1
next_arr.append(el)
queue+=next_arr
print(copy_board[1][m])
마무리
: BFS는 이렇게 최단거리를 측정할 때 '한칸씩 한칸씩' 서로 다른 경로를 탐색할 수 있다는 점에서 DFS와 차이가 나고, 그에 따라 DFS가 아닌 BFS로 이렇게 최단거리를 구할 수 있다는 점을 알아둬야할 것 같다.
