[PS] 2178) 미로 탐색

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

2178번: 미로 탐색

Silver1) 2178.미로 탐색

 

• 그래프 탐색, BFS, DFS

BFS, DFS 문제도 많이 풀어봤지만, 다시 한번 기본적인 문제로 정리하고 싶어 풀어봤다. DFS와 BFS는 한 번 이해하면 쉽게 다가오지만 막상 코드를 직접 짜려하면 잘 떠오르지 않을 수 있다. 또한, 문제마다 주어진 형식에 맞춰 조정할 필요도 있기 때문에 잘 다져놓는 것이 좋다.

 

해당 문제는 가장 기본적인 미로찾기이다. 보통 BFS가 DFS보다 퍼포먼스가 좋기 때문에 BFS를 많이 사용하며 이 문제에서의 특징은 출발부터 도착까지 거리를 계산해야 한다. 따라서 거리의 정보를 저장할 자리를 따로 마련해주어야 한다.

 

코드는 다음과 같다.

def getdata():
        n, m = map(int,input().split())
        board = list(list(map(int, input().rstrip())) for _ in range(n))
        return n, m, board

    n, m, board = getdata()
    need_visited, visited = deque(), dict()
    need_visited.append([0,0])
    visited[0,0] = 1
    while need_visited :
        nxt = need_visited.popleft()
        nx, ny = nxt[0], nxt[1]
        if nx == n-1 and ny == m :
            break
        if 0<=nx-1 and board[nx-1][ny] == 1 and (nx-1, ny) not in visited :
            need_visited.append([nx-1,ny])
            visited[nx-1, ny] = visited[nx, ny] + 1
        if 0<=ny-1 and board[nx][ny-1] == 1 and (nx, ny-1) not in visited :
            need_visited.append([nx,ny-1])
            visited[nx, ny-1] = visited[nx, ny] + 1
        if nx+1<n and board[nx+1][ny] == 1 and (nx+1, ny) not in visited :
            need_visited.append([nx+1,ny])
            visited[nx+1, ny] = visited[nx, ny] + 1
        if ny+1<m and board[nx][ny+1] == 1 and (nx, ny+1) not in visited :
            need_visited.append([nx,ny+1])
            visited[nx, ny+1] = visited[nx, ny] + 1
    print(visited[n-1, m-1])

굉장히 복잡해 보이지만, 그래프 구조를 미리 저장하지 않고 함수 내부에 썼을 뿐이다. 거리 정보를 저장할 자리는 visited를 dictionary로 설정하여 각 노드에 대한 value로 할당했다. 위부터 코드를 차례로 보자면 우선 시작지점인 0,0에서 각각 위, 아래, 왼쪽, 오른쪽에 노드가 존재하는지 확인한다. 노드가 존재하고, 노드의 값이 1이어서 움직일 수 있으며, 방문하지 않은 노드를 need_visited에 추가하여 바로 다음 while 반복을 통해 방문하도록 한다. 거리 정보는 visited에 노드를 추가할 떄, 이전 노드의 거리 + 1로 설정했다.