[python] 2178번 미로탐색

1. 문제 링크 및 문제

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

1-1 문제 요약

: N*M 크기의 배열에서 , (0,0) 부터 시작하여 (N,M)까지 좌표값이 1인 경우로만 가는데 최단경로

2. 해결 방법 생각해보자 ...

1. 최단경로라면 bfs로 접근해보자
2. BFS(x,y) 시작지점 및 종료시점, 탐색방법 생각해보기
   2-1 시작지점 : 0,0 에서 시작 (= bfs(0,0) )
   2-2 종료시점 : 리턴 x==N,y==M 일 때 리턴 , 아니면 2-3
   2-3 탐색방법 : 방향벡터를 사용하여 상하좌우 탐색

3. 코드

from collections import deque

N,M = map(int,input().split())
map = [list(map(int,input())) for _ in range(N)]
dx, dy = [-1,0,1,0],[0,-1,0,1] 

def bfs(x,y):
    q = deque()
    q.append((x,y))
    count = 0

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

        for i in range(4):
            xx, yy = x+dx[i], y+dy[i]
            if xx<0 or xx>=N or yy<0 or yy>=M:
                continue
            if map[xx][yy] == 1 :
                q.append((xx,yy))
                map[xx][yy] = map[x][y] + 1
    return map[N-1][M-1]

print(bfs(0,0))

그림으로 이해

아래 그림에서 배열의 값이 어떻게 변하는 지 살펴본다면 이해하기 더 쉬울 것이다

예시 : 백준 예제입력1
4 6
101111
101010
101011
111011

1. 초기상태의 배열

2. bfs(0,0) 그림으로 이해하기

각 문장 이해
1. q:(0,0)
: x,y = q.popleft() 에서 x=0, y=0 이 됨
2. q.append(1,0)
: 상하좌우 중 1 인 좌표를 q에 추가 (여기선 1,0 밖에 없음)
3. map[1][0] = map[0][0]+1
: 해당 좌표를 전 좌표값 + 1 을 해줌

상하좌우 중 1 이 하나밖에 없는 과정은 생략하였음.

q가 (0,4)일 때를 보면 알 수 있듯이, 모든 경로를 탐색하지만 경우의 수에 포함되지 않는다.

! 아차차

실수

처음 풀 때 대표적인 풀이방법인 큐를 사용한 bfs를 돌렸다.
이는 모든 경로를 방문, count +=1 이기에 모든 경우의 수를 더한 값이 나왔다 ! (길이 없는 곳 까지)
BFS에서 약간의 변형을 어떤 식으로 줘야할 지 고민하고, 방법을 알 수 있게 된 좋은 문제였다.