반응형
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
bfs를 이용해서 풀었다.
N, M = map(int, input().split())
def addVisited(element):
if element == '1':
return None
else:
return 0
graph = []
# 그래프 입력 받기
for j in range(N):
graph.append(list(input()))
graph[j] = list(map(addVisited, graph[j]))
# (0,0) queue에 삽입
queue = [(0, 0)]
graph[0][0] = 0
# queue가 empty가 될때 까지 4방향 반복하면서 insert, deque 반복
while queue:
currentLocation = queue.pop(0)
x, y = map(int, currentLocation)
distance = graph[x][y]
if x < N-1 and graph[x+1][y] == None:
graph[x+1][y] = distance + 1
queue.append((x+1, y))
if x > 0 and graph[x-1][y] == None:
graph[x-1][y] = distance + 1
queue.append((x-1, y))
if y < M - 1 and graph[x][y+1] == None:
graph[x][y+1] = distance + 1
queue.append((x, y+1))
if y > 0 and graph[x][y-1] == None:
graph[x][y-1] = distance + 1
queue.append((x, y-1))
print(graph[N-1][M-1]+1)
풀면서 2가지 트릭을 배웠다.
1. string을 list로 바꿀수 있다
list("abcd")를 하면 ['a','b','c','d'] 가 됨
2. map 메소드, 이건 자바스크립트랑 비슷하다.
map(func,iterator*) , 각각의 리스트 요소에 func를 적용하는건데
요건 여러개의 입력을 받을때 사용해봤다.
N,M = map(int, input().split())