백준 2178번 미로 탐색

이번 주에 풀었던 DFS/BFS 문제 시리즈는 모두 너무 어려웠고 지금 내가 할 수 없는 것에 너무 시간을 낭비하는 게 아닌가(? 물론 고민을 해봤다는 것은 지금 당장은 도움도 안 되고 기억에도 남지 않는 것 같아도 조금씩 쌓여서 최소한 사고력을 키우는 데 도움이 될 것이니 그렇게 조급할 필요는 없을 것이다.) 계속해도 될 것인가 고민이 많았던 게 사실이지만 열심히 고생한 결과 이 문제의 합격이 떠서 기쁘다. 그리고 정말 피곤하다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

문제 링크

https://www.acmicpc.net/problem/2178

풀이 전 계획과 생각

미로 탐색 문제를 처음에 봤을 때에는 도대체 이런 문제를 일주일 안에 풀 수 있을지에 대해 답답한 마음뿐이었는데 여러 가지 BFS 문제를 지금까지 풀어보고 나니 이 문제는 근본적으로 처음 풀어본 BFS 문제인 1697번 숨바꼭질과 거의 같은 구성으로 되어 있다. 물론 지난 주말만 해도 나는 이 문제나 그 문제나 왜 BFS인지 자체를 이해하지 못하고 있었지만! ㅋㅋㅋ

왜 최단거리 찾기가 BFS일까?
그래프나 트리나 아무튼 하나의 시작점에서 2,3,4,5,6...이라는 점으로 선이 뻗어나가 있다면

DFS는 2로 먼저 간 다음에 2에서 뻗어나간 점 11,12,13,14,15... 중에서 또 11을 찍고 11에서 또 101,102,103,104...가 뻗어나가고 있다면 또 101을 찍고... 이런 식으로 나간다.
반면에 BFS는 시작점에서 직접 연결된 점 2,3,4,5,6,7,8,9,10을 찍고
그 다음에 2에서 연결된 점을 다 찍고 3에서 연결된 점을 다 찍고 4에서 연결된 점을 다 찍고... 이렇게 탐색한다.

그러니까 시작점에서 거리가 1인 점을 다 뽑고, 그 다음에 거리가 1인 점들에서 직접 연결된 점, 즉 총 거리가 2인 점을 다 뽑고... 이런 순서로 찾아나가기 때문에 최초로 해당 도착점이 발견되는 시점이 그 도착점까지의 최단거리인 셈이다.

만약에 조사하려는 자료구조가 트리가 아니고 사이클이 있는 그래프라서 방문할 수 있는 경로가 여러 가지가 있다고 하더라도 먼저 찾은 경로가 더 적은 정점을 방문한 시점이기 때문에 특정 정점에 대해서는 먼저 찾은 거리가 최단 거리인 것 같다.

이처럼 처음에 1697번 숨바꼭질 문제를 풀 때에는 왜 BFS이며 BFS는 왜 그런 방식으로 탐색하는지 전혀 이해가 안 갔지만 이제는 할 수 있어서 보람을 느낀다.

본론으로 들어가서 문제를 풀어보려고 하는데 이 문제는 일단 입력 구조가 좀 헷갈린다.

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

왜 M,N이 아니고 N,M인지 모르겠는데 일단 이것 때문에 은근히 헷갈렸고 오타가 많이 발생할 뻔했다는 점을 일단 기록해 두고... ㅋㅋㅋ

두 개의 정수를 공백으로 구분하면서 입력하려면 일단 이렇게 입력한다.

import sys
N,M=map(int,sys.stdin.readline().split())

그리고 지금까지 백준 온라인 저지 문제에서 대부분 한 줄에 여러 값을 입력받으려면 공백으로 구분했는데 이번에는 붙어서 나간다. 예를 들어서 M=7이라면 하나의 7칸의 미로 구성은 1100111 이런 식으로 입력할 수 있다.

일단 하나의 문자열을 입력받아서 그것을 한 글자씩으로 이루어진 배열로 만들려면 list(input())이라고 하는 방법이 있다는 것을 이번 주에 처음 검색해보고 알았는데...

이 문제의 테스트 케이스 조건을 보면 한 줄에 최대 100글자씩 최대 100줄을 입력하는 과정 자체에서 파이썬에서 시간초과가 뜰 가능성이 높으니까 최대한 더 처리속도가 빠른 걸로 해보도록 해보면...

maze0 = list(map(int,list(sys.stdin.readline().strip())))

이런 식으로 할 수 있다고 한다. 뒤의 strip()은 왜 쓰냐면 라인을 통째로 입력받았을 때 마지막의 엔터키 입력도 포함할 수가 있기 때문에 앞뒤의 공백이나 널문자를 다 빼고 처리하도록 하는 것이라고 한다.
그리고 M칸의 미로를 N줄 입력 받으니까(아, 이렇게 한국말로 풀어서 썼을 때에 자연스러우니까 처음에 입력받을 때 M과 N을 입력받는 게 아니라 N과 M을 입력받는다고 했나? ㅋㅋㅋ) 이 과정을 N회 반복해서 하나의 2차원 배열 안에 다 넣어야 한다.

maze=[list(map(int,list(sys.stdin.readline().strip()))) for x in range(N)]

그리고 BFS는 한번 방문한 곳은 다시 방문하지 않기 때문에 방문 여부를 표시할 동일한 크기의 2차원 배열을 하나 더 만들어 놓고 초깃값은 모두 0으로 한다.

visited=[[0]*(M) for x in range(N)]

또한 각각의 칸의 최단거리를 측정하고 그것을 바탕으로 최단거리가 이미 측정된 칸에서 인접한 칸의 최단거리는 +1을 해주는 방법이기 때문에 각각의 칸의 현재 최단거리를 입력할 동일한 크기의 2차원 배열을 하나 더 만든다. 초깃값은 현재 구하지 않았다면 '무한대'이겠지만 이 문제의 입력값 조건이 가로 100 세로 100이 최대이기 때문에 모든 칸을 다 방문하더라도(물론 모든 칸이 다 방문할 수 있도록 0이 없이 모두 1로 개방되어 있다면 다른 지름길도 있겠지만 ㅋㅋㅋ) 도착점까지의 거리는 10000이 최대니까 그것보다 큰 값으로 정해 두었다. 물론 그냥 0으로 채워두고 방문여부는 앞의 visited[] 배열에서 판정해도 된다.

shortest = [[10001]*(M) for x in range(N)]

현재 최단거리를 업데이트하는 2차원 배열을 따로 만드는 이유는 각각의 정점의 최단거리는 이미 최단거리를 측정한 인접한 정점의 최단거리에 +1을 하는 방식으로 계산하기 때문이다.

예를 들어서 시작점의 최단거리는 1이기 때문에(현재 문제에 제시된 테스트 케이스와 정답을 보니 (0,0)의 최단거리를 0이 아니라 1이라고 간주하고 있다.) 시작점 바로 오른쪽 점 (0,1)의 최단거리는 (0,0)에 인접한 점이라는 사실을 바탕으로 1+1=2라고 하면 된다. 이렇게 인접한 점의 최단거리를 확정함으로써 (0,0) →(1,0) →(1,1) →(0,1) 같은 최단거리가 아닌 경로는 무시할 수 있다.

이제 여기에서 BFS는 어떻게 수행하는가?

물론 시작점 (0,0)에서 도착점 (N-1,M-1)까지 모두 구할 때까지 하면 된다.

• 최단거리를 탐색할 좌표들이 있는 deque가 있다. 물론 처음에는 시작점만 들어 있어서 [[0,0]]일 것이다. 시작점의 최단거리는 1로 초깃값이 정해져 있다.
• 현재 탐색할 좌표를 left pop 한다.
• 이것에 대해 비교할 대상은 x좌표만 +1 -1한 좌표, y좌표만 +1 -1한 좌표 총 4개가 있을 수 있으나 그렇게 계산한 좌표가 음수이거나 배열의 크기를 초과하는 경우를 제외하고 최단거리를 이미 구한 좌표인 경우도 제외한다. 당연히 길이 없는 좌표(0)인 경우도 제외한다.
• 이렇게 파악한 비교대상 좌표들의 최단거리는 현재 좌표의 최단거리의 +1로 업데이트해주고 방문 여부도 1로 바꾼 뒤에 탐색 deque에 right push해준다. 그러면 앞으로 각각의 좌표에 대해 아직 탐색하지 않은 인접 좌표들의 최단거리를 계산하는 과정을 비교 대상이 하나도 안 남을 때까지 반복할 수 있다.

그리고 마지막으로 shortest[N-1][M-1]에 저장된 값을 출력해주면 도착점의 최단거리를 출력하라는 문제의 풀이가 끝난다.

풀이 (코드 블록 첨부)

# 백준 2178번 미로 탐색 
import collections
import sys
N,M=map(int,sys.stdin.readline().split())
#houses = [list(map(int,list(input()))) for x in range(N)]
maze=[list(map(int,list(sys.stdin.readline().strip()))) for x in range(N)]
#print(maze)
visited=[[0]*(M) for x in range(N)]
#print(visited)
shortest = [[10001]*(M) for x in range(N)]
to_search = collections.deque([[0,0]])
comparison=[[-1,0],[1,0],[0,-1],[0,1]]
shortest[0][0]=1
while to_search:
    #print(to_search)
    current_loc = to_search.popleft()
    if visited[current_loc[0]][current_loc[1]]==0:
        visited[current_loc[0]][current_loc[1]]=1
        
        
    for compare in comparison:
        compare=[current_loc[0]+compare[0],current_loc[1]+compare[1]]
        #print(compare)
        if compare[0]>=0 and compare[0]<N \
           and compare[1]>=0 and compare[1]<M \
           and maze[compare[0]][compare[1]]==1 \
           and visited[compare[0]][compare[1]]==0:
            to_search.append(compare)
            visited[compare[0]][compare[1]]=1
            shortest[compare[0]][compare[1]]=shortest[current_loc[0]][current_loc[1]]+1
            
    
#print(shortest)
print(shortest[N-1][M-1])

풀이하면서 막혔던 점과 고민

지금까지 푼 다른 BFS 문제들은 정말 어려웠지만 그 문제들을 바탕으로 BFS에 대한 이해를 하고 나니 별로 막힘이 없이 잘 풀렸다.

그런데 앞의 두 문제도 코드가 거의 똑같은 것 같은데 왜 시간 초과가 뜰까? ㅠㅠ ㅋㅋㅋㅋㅋㅋㅋ 그런데 이미 여기까지 해보는 것만 해도 너무 시간이 오래 걸렸기 때문에 다음에 다시 해봐야겠다. ㅋㅋㅋ

풀이 후 알게된 개념과 소감

얼마만에 한 번에 합격하는 건지 모르겠다 ㅋㅋㅋ

그리고 파이썬에서 여러 값을 한 줄에 입력받는 방법을 다음에도 쓸 수 있게 기억해두어야겠다.

import sys
N,M=map(int,sys.stdin.readline().split())
#houses = [list(map(int,list(input()))) for x in range(N)]
maze=[list(map(int,list(sys.stdin.readline().strip()))) for x in range(N)]