[백준] 2178. 미로 탐색

문제 바로가기

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

 

💡 문제 요약

• N×M크기의 배열로 표현되는 미로가 있다.

• 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.

• 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

• 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

• 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.

• 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

• 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

ex)

입력	출력
4 6	15
101111
101010
101011
111011
4 6	9
110110
110110
111111
111101

 

💡 내 코드

import sys
from collections import deque

# 상하좌우 좌표
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(graph, x, y):
    que = deque()
    que.append((x, y))

    while que:
        x, y = que.popleft()

        # 현재 노드에서 상하좌우에 있는 노드들 중 방문할 수 있는 곳이 있는지 확인하기 위한 for문
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if not (0 <= nx < N) or not(0 <= ny < M):   # 새로 이동한 좌표 (nx, ny)가 그래프 범위 내인지 체킹, 아닐 경우 continue
                continue

            if graph[nx][ny] == 1:  # 현재 노드에서 상하좌우에 있는 노드들 중 갈 수 있는 곳이 있다면,
                graph[nx][ny] = graph[x][y] + 1   # 새로운 노드에 (현재 노드까지의 방문 횟수+1)을 넣어주고
                que.append((nx,ny)) # 큐에도 추가해준다.

    return graph[N-1][M-1]

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())

    graph=[]

    for _ in range(N):
        l = list(map(int, sys.stdin.readline().rstrip()))
        graph.append(l)

    ans = bfs(graph, 0, 0)
    print(ans)

 

💡 추가 풀이

ex)

• 그래프의 상하좌우를 돌면서 방문할 수 있는 노드를 방문하면서 graph에 갯수를 저장한다.
• 왼쪽 표가 graph로 주어지고 graph에 직접 방문한 노드 갯수를 추가할 경우, 오른쪽 표의 결과가 나온다.
  → 결국 graph[N-1][M-1]에 지나야 하는 최소의 칸 수가 저장됨.
  

 

💡 느낀점

• 그래프가 주어질 때 붙어있는 글자들이 주어지는 것을 처리하는 부분에서 조금 헷갈렸다.. rstrip()을 기억하자.
• 처음에는 graph 리스트 자체에 방문한 노드 갯수를 쌓아갈 생각을 하지 못하고 count 변수를 만들어서 노드를 지나갈 때 마다 1씩 추가하려고 했더니, 갈 수 있는 곳이 한 방향 이상인 노드에서 다음으로 어떤 노드로 건너가야할지 처리하기가 애매했다. 왜냐면 최소 갯수로 만들기 위한 방향을 찾는 과정까지 추가해야 하기 때문에..