[백준] 13565번: 침투 - 파이썬

🔈 문제

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.

예를 들어, Figure 1(a) 에서는 바깥쪽에서 공급된 전류가 안쪽까지 침투하지만, Figure 1(b)에서는 그렇지 못한다.

 

📝입력

첫째 줄에는 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

 

📑출력

바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다.그렇지 않으면 NO를 출력한다.

 

📚 문제 해석

첫번째 줄 마지막 줄로 갈 수 있는지 체크하면 되는 문제였다. 위에서 아래로 내려가니까 이동방향을 왼쪽, 오른쪽, 아래 이렇게 3가지만 두었다! 그러나 100%에서 틀렸습니다 판정을 받았다. 밑에서 내려갔다가 다시 위로 올라가는 경우를 생각하지 못했던 것이다ㅎ

 

📖 풀이

BFS를 사용하여 풀었다. 제일 위쪽 배열중 아직 방문하지 않은 0을 찾아 BFS를 시작하였다. 그리고 탐색을 마치고 제일 마지막 줄의 방문여부를 체크하여 YES 또는 NO를 출력하였다.

 

💻 코드

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

n,m = map(int,input().rstrip().split())
ans = "NO"
graph = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
visited = [[False for i in range(m)] for j in range(n)]
for i in range(n):
    graph.append(list(map(int,input().rstrip())))

# BFS 함수 정의
def bfs(x,y):
    queue= deque()
    visited[y][x] = True # 방문처리
    queue.append([x,y])
    while queue:
        a,b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if -1 < nx < m and -1 < ny < n:
                if not visited[ny][nx] and graph[ny][nx] == 0: # 아직 방문하지 않고 원소가 0이라면
                    visited[ny][nx] = True
                    queue.append([nx,ny])

for start in range(m):
    if graph[0][start] == 0 and not visited[0][start]: # 첫번째 줄 원소 값이 0이라면
        bfs(start,0) # BFS 탐색 시작

for end in range(m):
    if visited[-1][end]: # 마지막 줄을 방문하였다면
        ans = "YES"
        break
print(ans)

 

🔗 문제링크 : 침투

13565번: 침투