[백준/Python] 13565. 침투

 

 

• bfs(Flood Fill)을 이용하여 풀었다.

 

from collections import deque

N,M = map(int,input().split())
flag = "NO"												# flag값 설정
arr = [list(map(int,input())) for _ in range(N)]

def bfs(j,i):

    global flag
    q = deque([(j,i)])

    directY = [-1,1,0,0]
    directX = [0,0,-1,1]

    while q:
        y,x = q.popleft()

        for k in range(4):
            dy = directY[k] + y
            dx = directX[k] + x

            if dy < 0 or dy >= N or dx < 0 or dx >= M:  # 범위를 벗어난다면 continue
                continue
            if arr[dy][dx] == 0 and (dy == N-1):        # bfs를 돌다 제일 아래 쪽(inner side)에 도착하게 되면 flag 값 변경
                flag = "YES"
                arr[dy][dx] = 1
                q.append([dy,dx])
            elif arr[dy][dx] == 0:
                arr[dy][dx] = 1
                q.append([dy,dx])


for i in range(M):
    if arr[0][i] == 0:              # 침투가 가능한 제일 위쪽 (outer side)만 탐색하여 0이라면 함수 실행
        arr[0][i] = 1
        bfs(0,i)

print(f"{flag}")

 

 

왜 틀렸을까?

• bfs 함수에 들어가기전 if문 조건에 오타가 있었다. if arr[0][i] == 1: 로 잘못 입력했었는데도 채점이 50%이상 진행되어서 이쪽 부분을 다시 볼 생각을 못했다.