[백준] 13565 - 침투

1. 문제

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

13565번: 침투

 

2. 접근

1. '이코테 - 음료수 얼려먹기' 에서 사용되는 dfs 기본 로직을 사용하면 풀 수 있을것 같다

2. 위에서 board[x][y] == 0 부분이 있다면, dfs를 실행한다 ( dfs를 실행한다 -> 전류를 통하게 한다 )

3. 실행 후에 가장 아래 열에서 board[n-1][i] == 2 즉, 전류가 통했다면 flag == True로 변경해서 'YES'를 통하지 않았다면 'NO'를 출력하면 된다.

 

3. 풀이

# 13565 실버 2
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n,m = map(int,input().split())

board = []
for i in range(n):
    board.append(list(map(int,input().rstrip())))

def dfs(x,y):
    if 0<=x<n and 0<=y<m and board[x][y] == 0:
        board[x][y] = 2
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)

for j in range(m):
    if board[0][j] == 0:
        dfs(0,j)

flag = False
for j in range(m):
    if board[n-1][j] == 2:
        flag = True
        break

if flag == True:
    print('YES')
else:
    print('NO')