Baekjoon 2178 | 미로 탐색(Python)

📌문제

SILVER1 / bfs / 그래프 탐색 / 그래프

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

📌문제 분석 및 설계

문제를 봤을 때, [ 최소의 칸 수 / 입력 처리 ]가 핵심이라고 생각했다.

완전히 기본중에 기본 bfs문제라, bfs 처음 연습할 때 좋은 문제다.

 

따라서 아래와 같은 요소들로 설계를 했다.

1.  bfs로 탐색하면서 이전 위치를 기록하고, 탐색을 마친 후 N,M부터 역으로 1,1까지 가면서 경로추적하며 최소 칸 수 계산

2. grid를 줄 때, 입력을 붙여서 주기때문에 따로 처리

 

생각해보니 경로추적이 불필요하다고 생각해 최단거리 추적하는 방식으로 변경했다.

두 버전 모드 코드를 업로드했다.

 

📌소스 코드

#경로 추적 버전
from collections import deque
dxs,dys=[-1,0,1,0],[0,1,0,-1]
n,m=map(int,input().split())

grid=[[0]*m for _ in range(n)]
for i in range(n):
    for j,k in enumerate(input()):
        grid[i][j]=int(k)

def can_go(x,y):
    return 0<=x<n and 0<=y<m and grid[x][y]==1

path=[[0]*m for _ in range(n)]

def bfs():
    q=deque([(0,0)])
    path[0][0]=1
    while q: #deque는 비어있을 때 False로 평가
        x,y=q.popleft()
        for dx,dy in zip(dxs,dys):
            nx,ny=x+dx,y+dy
            if can_go(nx,ny) and path[nx][ny]==0:
                if (nx,ny)==(n-1,m-1):
                    path[nx][ny]=(x,y)
                    return 
                else:
                    q.append((nx,ny))
                    path[nx][ny]=(x,y)
               
bfs()
x,y=n-1,m-1
cnt=1
while (x,y)!=(0,0):
    x,y=visited[x][y]
    cnt+=1

print(cnt)

#최단거리 추적 버전
from collections import deque
dxs,dys=[-1,0,1,0],[0,1,0,-1]
n,m=map(int,input().split())

grid=[[0]*m for _ in range(n)]
for i in range(n):
    for j,k in enumerate(input()):
        grid[i][j]=int(k)

def can_go(x,y):
    return 0<=x<n and 0<=y<m and grid[x][y]==1

distance=[[0]*m for _ in range(n)]

def bfs():
    q=deque([(0,0)])
    distance[0][0]=1
    while q: #deque는 비어있을 때 False로 평가
        x,y=q.popleft()
        for dx,dy in zip(dxs,dys):
            nx,ny=x+dx,y+dy
            if can_go(nx,ny) and distance[nx][ny]==0:
                q.append((nx,ny))
                distance[nx][ny]=distance[x][y] + 1
    return distance[n-1][m-1]  # 도착 지점의 최단 거리 반환

print(bfs())