알고리즘/백준
1261번 알고스팟 백준 파이썬
글을 쓰는 개발자
2020. 12. 15. 20:15
반응형
문제:www.acmicpc.net/problem/1261
1261번: 알고스팟
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미
www.acmicpc.net
이 문제를 풀기 전에 숨바꼭질3을 먼저 풀어볼 것을 권장한다. 이 두문제는 비슷한 면이 많이 있다.(www.acmicpc.net/problem/13549)
여기에서 중요한 포인트는 어떤 것을 먼저 할 것이냐를 결정하는 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import sys
from collections import deque
N,M=map(int,sys.stdin.readline().rstrip().split())
graph = [list(map(int,sys.stdin.readline().rstrip())) for _ in range(M)]
visited =[[False]*N for _ in range(M)]
dy=[1,-1,0,0]
dx=[0,0,1,-1]
def scope(y,x):
if y>=0 and y<M and x>=0 and x<N:
return True
else:
return False
def bfs():
q=deque()
q.append([0,0])
visited[0][0]=True
while q:
fy,fx=q.popleft()
if fy==M-1 and fx ==N-1:
print(graph[fy][fx])
break
for i in range(4):
my=fy+dy[i]
mx=fx+dx[i]
if scope(my,mx):
if not visited[my][mx] and graph[my][mx]==0:
visited[my][mx]=True
graph[my][mx]=graph[fy][fx]
q.appendleft([my,mx])
elif not visited[my][mx] and graph[my][mx]!=0:
visited[my][mx]=True
graph[my][mx]=graph[fy][fx]+1
q.append([my,mx])
bfs()
|
cs |
위의 설명을 코드로 표현하면 다음과 같이 된다.
반응형