[백준 2178번 / 실버1] 미로 탐색 - (Graph Traversal)

문제링크 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

이 문제는 최소경로를 찾는 문제이고 각각 간선(edge)의 가중치가 동일하므로 BFS를 이용해도 무방하다.

 

핵심은 dx,dy라는 방향벡터를 사용하는 것과,

미로의 정보를 나타내는 data라는 2차원 리스트랑은 별개로

특정 칸을 방문하기 위해 지나야 하는 최소 칸의 정보를 담고있는 visited라는 2차원 리스트를 추가로 만드는것이다.

 

from collections import deque

def BFS(data):
  visited=[[0]*M for i in range(N)]
  #하,우,상,좌
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  queue=deque()
  queue.append([0,0])
  visited[0][0]=1
  while queue:
    x,y=queue.popleft()
    if(x==N-1 and y==M-1):
      return visited[x][y]
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i] #x,y는 현재 위치. nx,ny는 바뀔 예정인 위치
      if 0<=nx<N and 0<=ny<M:
        if data[nx][ny]==1 and visited[nx][ny]==0:
          queue.append([nx,ny])
          visited[nx][ny]=visited[x][y]+1

N,M=map(int,input().split())
data=[]
#2차원 리스트에 입력하는 문자열을 리스트로 변환 후 채우기
for j in range(N):
  data.append(list(map(int,input())))
print(BFS(data))

 

+++

data라는 리스트에 입력값을 채워넣는 부분의 코드를 보자.

data=[]
for j in range(N):
  data.append(list(map(int,input())))

이 코드를 좀 더 짧게, 파이써닉하게 바꿔보자!!

data=[list(map(int,input())) for _ in range(N)]

list comprehension을 이용해서 더 간단한 코드를 알아보았다.

앞으로 잘 활용 할것!!

 

 

 

++

추가적으로 코드 길이를 더 줄여보았다.

visited라는 2차원 리스트 없이 구현해 보았다.

BFS를 통해 값이 1인 칸을 방문하면서 길을 찾아 나갈때

방문을 하면 해당 노드값을 그 전 방문 노드값+1로 바꿔버린다.

그러면 최종적으로 노드값은 해당 노드를 방문하기 위해 필요한 최단경로가 된다.

from collections import deque

def BFS(data):
  queue=deque()
  queue.append([0,0])
  dx=[0,1,0,-1]
  dy=[1,0,-1,0]
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if(0<=nx<n and 0<=ny<m):
        if(data[nx][ny]==1):
          queue.append([nx,ny])
          data[nx][ny]=data[x][y]+1
  return data[n-1][m-1]

n,m=map(int,input().split())
data=[list(map(int,input())) for _ in range(n)]
print(BFS(data))