음료수 얼려 먹기

출처:: 

분류:: DFS

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

 1. DFS

#음료수 얼려 먹기
#
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
dh=[-1,1,0,0]
dw=[0,0,-1,1]

visited=[[0]*m for _ in range(n)]
board = [list(map(int, input())) for _ in range(n)]

def DFS(h,w):
    visited[h][w] = 1
    for i in range(4):
        nh=h+dh[i]
        nw=w+dw[i]
        if nh>=n or nh<0 or nw>=m or nw<0:
            continue
        if board[nh][nw]==1 or visited[nh][nw]==1:
            continue
        DFS(nh,nw)

def Solve():
    cnt=0
    for i in range(n):
        for j in range(m):
            if visited[i][j]==0 and board[i][j]==0:
                DFS(i,j)
                cnt+=1
    return cnt
res=Solve()
print(res)

  2. DFS - 상,하,좌, 우를 재귀적으로 호출한 경우

#음료수 얼려 먹기
#
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
dh=[-1,1,0,0]
dw=[0,0,-1,1]

visited=[[0]*m for _ in range(n)]
board = [list(map(int, input())) for _ in range(n)]

def DFS(h,w):

    if h>=n or h<0 or w>=m or w<0:
        return False
    if board[h][w]==1 or visited[h][w]==1:
        return False
    visited[h][w] = 1
    DFS(h - 1, w)
    DFS(h , w - 1)
    DFS(h + 1, w)
    DFS(h , w + 1)
    return True

def Solve():
    cnt=0
    for i in range(n):
        for j in range(m):
            if visited[i][j]==0 and board[i][j]==0:
                if DFS(i,j) == True:
                    cnt+=1
    return cnt
res=Solve()
print(res)

 

3. 오답원인

 

4. 알게된 점