B)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,BFS

N행M열이 주어졌다고 가정하였을 때, 결국 N행에 도달하게 된다면 전류는 안쪽으로 잘 통하게 되는 것 이기 때문에, 그래프의 탐색 알고리즘을 사용하면 풀 수 있는 문제이다.

구현(DFS)
1.먼저 1행의 값이 0인 곳을 파악한다.
2.0인 곳 부터, 4방향(동,서,남,북) 탐색을 진행하며, 값이 0일경우 다시 그 지점 부터 탐색을 시작한다.
3.만약 탐색 지점이 N행에 도달하면, "YES"를 출력한다.

import sys
sys.setrecursionlimit(10**8) #재귀 리미트 설정

def dfs(x,y):
    global result
    global visited
    visited[x][y] = True
    if x == N-1: #N행에 도달할 경우 return True
        result = True
        return result
    graph[x][y]=2
    for i in range(4): #4방향 탐색
        a,b = x + dx[i],y + dy[i] 
        if 0 <= a < N and 0 <= b < M:
            if not visited[a][b] and graph[a][b]==0:
                visited[a][b] = True
                dfs(a,b)


N,M = map(int,sys.stdin.readline().split())

graph = [list(map(int,list(sys.stdin.readline().rstrip())))for _ in range(N)]
visited = [[False]*(M) for _ in range(N)]
result = False
dx = [0,1,0,-1]
dy = [1,0,-1,0]

for j in range(M): #첫 행에서, 0인 원소를 찾는 과정
    if graph[0][j] ==0:
        dfs(0,j)
        if result:
            print("YES")
            break
if not result:
    print("NO")

결국 가장 안쪽으로 들어가야하는 것이기 때문에, 첫 행에서 0을 찾고(출발점), 만약 안쪽으로 다 못들어간다면, 다시 위로 올라가서, 그 출발점이 아닌 다른 출발점에서 경로를 찾는 방식이다.
그렇다면 BFS로는 어떻게 구현할 수 있을까?

구현(BFS)
1.입력받은 행렬을 1행1열부터 같은 높이에 있는 "0"을 탐색한다.
2.탐색한 "0"부터 4방향 탐색하여, 만약 "0"이 존재한다면 큐에 넣는다
3.큐에서 이전 "0"의 위치를 빼내어, 그 위치부터 다시 4방향 탐색을 한다.
4.위 과정을 계속하여, 만약 N행에 위치하게 된다면, "YES"를 출력한다.

import sys
from collections import deque #큐를 사용하기 위한 라이브러리

def bfs():
    while queue:
        a,b = queue.popleft() #왼쪽부터 뽑음 (왼쪽이 가장 먼저 들어간 정보)
        if a == N-1:
            print("YES")
            return
        for i in range(4):
            a , b = a+dx[i],b+dy[i]
            if 0 <= a < N and 0 <= b < M:
                if not visited[a][b] and graph[a][b] == 0:
                    visited[a][b] = True
                    queue.append((a,b))
    print("NO")





dx = [0,1,0,-1]
dy = [1,0,-1,0]
N,M = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().rstrip()))for _ in range(N)]
visited = [[False]*M for _ in range(N)]

queue = deque()
for i in range(M): #첫 열 "0"의 위치를 큐에 넣어둠(시작점)
    if graph[0][i]==0:
        queue.append((0,i))
        visited[0][i] = True
bfs()

DFS,BFS의 개념을 잘 알고 있다면, 풀 수 있는 문제였다.
하지만 잔 실수가 너무 많아서 런타임 에러가 수도 없이 떴다..