백준 13565 침투 풀이 ( 파이썬 )
https://www.acmicpc.net/problem/13565
13565번: 침투
첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않
www.acmicpc.net
맨 윗줄이 0인 부분만 q에 먼저 담고 bfs를 돌려서 맨 밑줄(index:m-1)에 도달한다면 멈춘다.
from collections import deque
m,n=map(int,input().split())
dx=[0,1,0,-1]
dy=[1,0,-1,0]
arr=[]
visited=[[False]*n for _ in range(m)]
q=deque()
for i in range(m):
arr.append(list(map(int,input())))
# 맨 윗줄이 0인 부분만 q에 저장
for j in range(n):
if i==0 and arr[i][j]==0:
arr[i][j]=2
q.append((i,j))
flag=False
while q:
cx,cy=q.popleft()
if cx==m-1:
flag=True
break
for i in range(4):
nx=cx+dx[i]
ny=cy+dy[i]
if nx<0 or ny<0 or nx>=m or ny>=n:
continue
if arr[nx][ny]==0:
if nx==m-1:
flag=True
break
arr[nx][ny]=2
q.append((nx,ny))
if flag:
break
if flag:
print("YES")
else:
print("NO")
[ baekjoon ] 민서의 응급 수술 20955번 ( python ) (4) | 2021.06.21 |
---|---|
[ baekjoon ] 섬의 개수 4963번 ( python ) (0) | 2021.06.15 |
[ baekjoon ] 군사 이동 11085번 ( python ) (0) | 2021.06.08 |
[ baekjoon ] 전설의 JBNU 12757번 ( python ) (0) | 2021.06.06 |
[ baekjoon ] 디지털시계 1942번 ( python ) (0) | 2021.06.05 |