[baekjoon] 백준 13565번(파이썬): 침투

문제

13565번: 침투

- 인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다.

- 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다.

- 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다.

- 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다.

- 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.

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

- 격자의 크기를 나타내는  M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다.

- M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다.

- 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.

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

 

알고리즘

- 바깥쪽에서 전류가 흐르면 안쪽까지 침투하는지 dfs 탐색을 통해 수행한다.

- dfs 탐색 후 2차원 리스트 안쪽에 침투한 전류가 있다면 'YES' 출력, 그렇지 않다면 'NO' 출력

코드

import sys
sys.setrecursionlimit(10**6) # 재귀 허용 깊이를 수동으로 늘려주는 코드


# dfs 탐색
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에 즉시 종료
    if x <= -1 or x >= m or y <= -1 or y >= n:
        return False

    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        # 해당 노드 방문 처리 (전류 이동)
        graph[x][y] = 2

        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)

        return True
    return False


m, n = map(int, sys.stdin.readline().split())

# 2차원 리스트의 맵 정보를 입력 받는다.
graph = []
for _ in range(m):
    graph.append(list(map(int, input())))

# 바깥쪽에서 전류가 흐르면 안쪽까지 침투하는지 DFS 탐색으로 수행
for i in range(n):
    dfs(0, i)

# 2차원 리스트 안쪽에 침투한 전류가 있다면 YES 출력 없다면 NO 출력
if graph[m - 1].count(2):
    print("YES")
else:
    print("NO")

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법