[210928] 백준 13565 침투 실버2 문제풀이 python

 

- 알고리즘 분류 : 그래프이론, 그래프탐색, 너비우선탐색, 깊이우선탐색

 

 

---

 

 

#백준 13565 침투

from collections import deque
import sys
input = sys.stdin.readline


def bfs(y,x):
    q = deque()
    q.append((y,x))
    graph[y][x]=2
    while q:
        y,x=q.popleft()
        graph[y][x]=2
        for dy,dx in d:
            Y,X = y+dy, x+dx
            if (0<= Y < M) and (0<=X<N) and graph[Y][X]==0:
                q.append((Y,X))
                graph[Y][X] =2


M,N = map(int,input().split()) #2차원 M*N 격자
graph=[list(map(int,list(input().strip()))) for _ in range(M)]
d= [(1,0),(-1,0),(0,1),(0,-1)] #상하좌우 
for j in range(N):
    if(graph[0][j]==0):
        bfs(0,j)

print("YES" if 2 in graph[-1] else "NO")

 

 

 

 

바깥쪽에 공급된 전류가 안쪽까지 들어올 수 있는 지 찾는 문제

 

지금까지 3번정도 푼 것 같은데 매번 모르겠어서 이번에도 풀이를 봤다. 아무래도 이해를 안 하고 외우려고만 한 문제인것 같다.. ㅠ 이번엔 이해하고 코드 안보고 다시 적어봤는데 bfs/dfs 문제는 많이 많이 풀어봐야할 것 같다.

 

 

 

---