[백준 13565번]침투 파이썬 풀이

침투 

1 초

512 MB

8389

3783

2827

44.415%

문제

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

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

 

 

 

(a) The current percolates.

(b) The current does not percolate.

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

 

입력

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

출력

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

그렇지 않으면 NO를 출력한다.

예제 입력 1

5 6
010101
010000
011101
100011
001011

예제 출력 1

NO

예제 입력 2

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

예제 출력 2

YES

 

 

BFS나 DFS를 이용하면 쉽게 풀 수 있는 문제이다. 나는 BFS가 더 익숙하므로 BFS로 풀어보았다.

문제의 핵심은 배열의 맨 윗줄에서 맨 아래쪽으로 방문이 가능한지를 묻는 문제이므로 맨 윗줄에 0인 좌표가 없다면 bfs를 수행할 필요 없이 NO를 출력하면 되고, 맨 윗줄에 0인 좌표들이 있다면 해당 좌표들을 대상으로 bfs를 수행하여 바닥 좌표에 도달하였다면 bfs를 중단하고 "YES"를 출력하도록 하면 된다.

 

아래 데이터를 대상으로 설명해보겠다. 테스트 케이스1을 설명을 위해 조금 수정하였다.

5 6 010101 010000 011101 100001 001011

맨 윗공간에 0인 좌표는 [0,0], [0,2], [0,4] 이므로 해당 좌표들을 대상으로 bfs를 수행한다. [0,0] 좌표에서는 [2,0]에서 끝까지 도달하지 못하므로 bfs를 종료하고, [0,2]좌표에 대해서 bfs를 수행하면 [4,3]에서 배열의 가장 마지막 행인 4번째 행에 도달할 수 있으므로 그 시점에서 탐색을 종료하고 "YES"를 출력할수 있다. 이미 전기가 통하는것을 확인하였으므로 더이상 다른 좌표들로 bfs를 수행할 필요 없이 프로그램을 종료해도 괜찮다.

 

위 아이디어를 코드로 옮기면 다음과 같다.

import sys
from collections import deque
m, n = map(int, input().split())

graph = [list(input()) for _ in range(m)]

# 방문정보를 표현할 배열
visited = [[False]*n for _ in range(m)]

# 네가지 방향 정의
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def bfs(s, e):
    queue = deque()
    queue.append([s, e])
    visited[s][e] = True  # 시작 좌표 방문처리
    while queue:
        x, y = queue.popleft()
        # 목적지에 도달하였다면
        if x == m-1:  # 가장 아래칸에 도달하였다면
            return True  # 탐색 성공의 의미로 True 리턴
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 영역을 벗어나지 않고, 아직 방문하지 않은 좌표에 대해서만
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                if graph[nx][ny] == '0':  # 전기가 통하는 영역으로만 탐색 수행
                    visited[nx][ny] = True  # 방문처리
                    queue.append([nx, ny])  # 해당 좌표 삽입
    # 탐색 결과 목적지에 도달하지 못하였다면 실패의 의미로 False리턴
    return False


# 입력받은 배열을 탐색하며 맨 윗쪽에 '0'인 공간을 찾으면 해당 좌표에 대해 bfs수행
# 만약 맨 윗줄에 '0'인 공간이 없다면 전기가 통하지 않는 물질이므로 bfs없이 "NO"출력
for i in range(n):
    if graph[0][i] == '0':
        if bfs(0, i):
            print("YES")
            sys.exit(0)  # 프로그램 종료
print("NO")

 

 

https://www.acmicpc.net/problem/13565

13565번: 침투