백준 : 미로 탐색 - 2178

입력

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

출력

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

예제 입력 1 

4 6
101111
101010
101011
111011

예제 출력 1 

15

예제 입력 2 

4 6
110110
110110
111111
111101

예제 출력 2 

9

예제 입력 3 

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3 

38

ㅁ

예제 입력 4 

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4 

13

 

이 문제는 사실 백준 문제 중에 1012번, [이코테] : DFS/BFS (미로 탈출) 를 보면 유사한 문제와 같다.

 

import sys
from collections import deque

# sys.stdin.readline을 짧은 변수명으로 설정
input = sys.stdin.readline

n,m = map(int,input().split())

graph = []
for _ in range(n):
    graph.append(list(map(int,input().rstrip()))) # rstrip 안하면 개행 문자 포함이여서 꼭 하기

x,y = 1,1

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

def BFS(x,y):
    queue = deque([(x,y)])
    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny <0 or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))
        
    return graph[n-1][m-1] # 마지막 그래프까지 어떻게 도달했는지 거리 반환을 의미함.

# 실제 위치는 1,1이지만 그래프 인덱스 기준으로는 0,0!
print(BFS(0,0))

다음과 같이 큐에 넣고 각 행을 위치로 기억하여 좌표값대로 움직일 때 마다 그래프의 값을 1씩 증가하여 업데이트 해주는 로직으로 구현하면 따로 count 없이 구현이 가능할 수 있다.