'미로찾기' 태그의 글 목록

미로찾기

놀만큼논사람 2022. 7. 5. 17:45

2022. 7. 5. 17:45

2178번: 미로 탐색

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

www.acmicpc.net

내 풀이

from collections import deque

def solution():

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

graph=[]

for _ in range(n):

graph.append(list(map(int,input())))

dx=[1,-1,0,0]

dy=[0,0,1,-1]

queue = deque([(0,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 graph[nx][ny]==1:

graph[nx][ny]= graph[x][y] +1

queue.append((nx,ny))

return graph[n-1][m-1]

print(solution())

다른사람의 풀이

BFS 대표 문제이다.

n x m 크기의 그래프를 받아주고

graph를 초기화 해준다.

dx -> x가 상하좌우로 이동할때 x의 값

dy -> y가 상하좌우로 이동할때 y의 값

deque의 특징이라고 한다면 좌,우 어디로든 insert,pop할 수 있다.