2178-미로탐색

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

2178번: 미로 탐색

 

그래프 탐색 문제의 또다른 대표 형식인 길찾기 문제이다. 길찾기 문제의 경우 방향값을 미리 코드에 짜두고 for문으로 순회하는 방식의 기법을 항상 기억하고 있어야 한다.

그리고 이 문제의 경우 시작점이 정해져 있고, 도착점까지의 최단거리를 구해야 하기 때문에 한쪽으로 끝까지 들어가는 DFS보다 자신을 기준으로 한레벨씩 나아가는 BFS 방식이 적합하다. 따라서 이 문제의 코드를 짜기 전에

- 길찾기 문제 -> 좌표 활용

- 최단거리 -> BFS -> 큐

이렇게 두 가지를 미리 정해놓고 들어가자!

 

이 문제에서 짚고 넘어갈 부분은 크게 두 가지가 있었는데, 먼저 배열 입력의 형식이 

101111

101010

101011

111011

이런 형태로 숫자들이 붙어서 들어온다는 것이었다.

이러한 경우에는 int(input())의 형태보다 list(str(input())) 의 형태로 띄어서 입력 받은 후 이를 int형으로 변환하거나 문자형 그대로 써도 된다.

 

두 번째는 check 설정의 위치였다. 다음과 같은 코드를 짜고 돌려봤는데 시간초과가 나왔다.

from collections import deque
import sys
input= sys.stdin.readline
N, M = map(int,input().split())
adj = []
for _ in range(N):
    adj.append(list(str(input())))

dy = (0,1,0,-1)
dx = (1,0,-1,0)

chk = [[0]*M for _ in range(N)]

def checkadj(y,x):
    if 0 <=y <M and 0<= x <N:
        return True

dq = deque()
def bfs(y, x, count):
    dq.append((y,x, count))
    while dq:
        ny, nx, nxtcount = dq.popleft()
        chk[nx][ny] = 1		# 여기가 문제!!
        if nx == N-1 and ny == M-1:
            return nxtcount            
        for i in range(4):
            newy, newx = ny+dy[i], nx+dx[i]            
            if checkadj(newy, newx) and chk[newx][newy] == 0  and adj[newx][newy] == '1':
                dq.append((newy,newx, nxtcount+1))
            
print(bfs(0,0,1))

문제는 방문했던 위치를 표시하는 chk 배열의 변경 위치였다. 위의 코드에서는 좌표를 큐에 넣은 후 그 큐에서 빼낼때 체크를 하는 형식인데 이러한 경우 같은 위치의 좌표값이 큐에 중복해서 들어가 있을 수 있다. 큰 차이가 나지 않을 것이라 생각했지만 입력값이 커질 경우 시간초과가 날 정도로 크리티컬한 부분이었다. 

따라서 chk 값을 변경해주는 부분을 큐에 삽입할때로 바꾸어서 문제를 통과할 수 있었다.

from collections import deque
import sys
input= sys.stdin.readline
N, M = map(int,input().split())
adj = []
for _ in range(N):
    adj.append(list(str(input())))

dy = (0,1,0,-1)
dx = (1,0,-1,0)

chk = [[0]*M for _ in range(N)]

def checkadj(y,x):
    if 0 <=y <M and 0<= x <N:
        return True

dq = deque()
def bfs(y, x, count):
    dq.append((y,x, count))
    chk[x][y] = 1
    while dq:
        ny, nx, nxtcount = dq.popleft()
        #chk[nx][ny] = 1 여기에서
        if nx == N-1 and ny == M-1:
            return nxtcount            
        for i in range(4):
            newy, newx = ny+dy[i], nx+dx[i]            
            if checkadj(newy, newx) and chk[newx][newy] == 0  and adj[newx][newy] == '1':
                dq.append((newy,newx, nxtcount+1))
                chk[newx][newy] = 1	# 여기로 변경!!!
            
print(bfs(0,0,1))