2178. 미로 탐색 (Silver I)

✔️ 문제

2178 문제 보기

✔️ 문제 분석 및 해결 과정 설계

• 문제 이해

  • N * M 크기의 배열로 표현되는 미로
    • 1 : 이동할 수 있는 칸
    • 0 : 이동할 수 없는 칸
  • (1, 1) 에서 출발해 (N, M) 의 위치로 이동할 때 지나야 하는 최소의 칸 수 구하기

• 입력

  • 첫째 줄 : N, M (2 ≤ N, M ≤ 100)
  • 다음 N개의 줄 : M개의 정수로 미로가 주어짐
  • 각각의 수들은 붙어서 입력으로 주어짐

• 출력

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

• 문제 풀이 아이디어

  • 길찾기 문제 (좌상단 → 우하단)
  • BFS를 사용해 최단 경로 탐색

✔️ 문제 해결 과정

• BFS 구현을 위해 deque 이용

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
board = [input() for _ in range(N)] # N줄의 스트링으로 입력 받기

• 경로를 찾기 위한 x, y 방향 값인 dy, dx 초기화

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

• bfs() 구현
  • 방문했던 곳을 재방문하는 상황을 방지하기 위해 chk 초기화
  • dq.popleft()를 반복하며 dq가 존재할 동안 4가지 방향 탐색

def bfs():
    chk = [[False] * M for _ in range(N)]
    chk[0][0] = True #(1, 1)부터 방문하므로 첫번째 노드의 chk 여부를 True로 설정
    dq = deque()
    dq.append((0, 0))
    while dq:
        y, x = dq.popleft()
        for k in range(4):
            ny = y + dy[k] # 다음 y 후보 좌표
            nx = x + dx[k] # 다음 x 후보 좌표

• 후보 좌표 조건 체크
  • ny, nx가 N, M의 범위 내의 정수인가?
  • board[ny][nx]의 값이 1인가? → 방문할 수 있는 칸인가?
  • chk[ny][nx]의 값이 False인가? → 방문하지 않은 칸인가?

def is_valid_coord(y, x):
    return 0 <= y < N and 0 <= x < M

def bfs():
    chk = [[False] * M for _ in range(N)]
    chk[0][0] = True #(1, 1)부터 방문하므로 첫번째 노드의 chk 여부를 True로 설정
    dq = deque()
    dq.append((0, 0))
    while dq:
        y, x = dq.popleft()
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and board[ny][nx] == '1' and not chk[ny][nx]:
                chk[ny][nx] = True
                dq.append((ny, nx))

• 방문한 칸의 개수인 cnt를 bfs 로직에 추가
  • dq에 ncnt도 함께 dq.append()

def bfs():
    chk = [[False] * M for _ in range(N)]
    chk[0][0] = True #(1, 1)부터 방문하므로 첫번째 노드의 chk 여부를 True로 설정
    dq = deque()
    dq.append((0, 0, 1))
    while dq:
        y, x, cnt = dq.popleft()
        if y == N - 1 and x == M - 1: # 가장 마지막 (N, M)에 도착한 경우
            return cnt
        ncnt = cnt + 1 # 칸 개수
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and board[ny][nx] == '1' and not chk[ny][nx]:
                chk[ny][nx] = True
                dq.append((ny, nx, ncnt))

💻 최종 코드

import sys
from collections import deque
input = sys.stdin.readline
dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)
N, M = map(int, input().split())
board = [input() for _ in range(N)] # N줄의 스트링으로 입력 받기
def is_valid_coord(y, x):
    return 0 <= y < N and 0 <= x < M
def bfs():
    chk = [[False] * M for _ in range(N)]
    chk[0][0] = True #(1, 1)부터 방문하므로 첫번째 노드의 chk 여부를 True로 설정
    dq = deque()
    dq.append((0, 0, 1))
    while dq:
        y, x, cnt = dq.popleft()
        if y == N - 1 and x == M - 1: # 가장 마지막 (N, M)에 도착한 경우
            return cnt
        ncnt = cnt + 1 # 칸 개수
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and board[ny][nx] == '1' and not chk[ny][nx]:
                chk[ny][nx] = True
                dq.append((ny, nx, ncnt))
print(bfs())