DFS&BFS 문제

1. 음료수 얼려먹기

(1) 문제 

(2) DFS 이용 

1)

def DFS(graph, r,c, N,M):
    
    graph[r][c]=1
    #상하좌우
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]

    for i in range(4):
        x= r+dx[i]
        y= c+dy[i]
        if(x<0 or y<0 or x>=N or y>=M):
            continue
        elif(graph[x][y]!=1):
            DFS(graph, x, y, N,M)

    return True
        
def main():
    N,M = map(int, input().split())
    graph = []

    for i in range(N):
        graph.append(list(map(int,list(input()))))
    cnt=0
    for i in range(N):
        for j in range(M):
            if(graph[i][j]!=1):
                if(DFS(graph,i,j,N,M)==True):
                    cnt+=1
    print(cnt)




if __name__=="__main__":
    main()

2)

def DFS(graph, r,c, N,M):
    if(r<0 or c<0 or r>=N or c>=M):
        return False
    elif (graph[r][c]==1):
        return False
    elif(graph[r][c]==0):
        graph[r][c]=1
        #상하좌우
        DFS(graph, r-1, c, N,M )
        DFS(graph, r+1, c, N,M)
        DFS(graph, r, c-1, N,M)
        DFS(graph, r, c+1, N,M)
        return True
    
    return False

def main():
    N,M = map(int, input().split())
    graph =[]
    for i in range(N):
        graph.append(list(map(int, list(input()))))
    cnt=0
    for i in range(N):
        for j in range(M):
            if(DFS(graph, i,j,N,M)==True):
                cnt+=1
    print(cnt)

                     
if __name__=="__main__":
    main()

2. 미로 탈출

from collections import deque

def BFS(graph, N,M, visited):
    queue = deque()
    r=0
    c=0
    #상하좌우
    dx = [-1,1,0,0]
    dy=[0,0,-1,1]

    queue.append([r,c])
    while(queue):
        now=queue.popleft()
        r = now[0]
        c= now[1]
        if(visited[r][c]==True):
            continue
        visited[r][c]=True

        for i in range(4):
            x= r+dx[i]
            y= c+dy[i]
            if(x<0 or y<0 or x>=N or y>=M):
                continue
            elif(visited[x][y]==True):
                continue
            elif(graph[x][y]!=0):
                graph[x][y]=graph[r][c]+1
                queue.append([x,y])
            
    for i in range(N):
        for j in range(M):
            print(graph[i][j], end=" ")
        print("")


def main():
    N,M = map(int, input().split())
    graph = []
    for i in range(N):
        graph.append(list(map(int, list(input()))))
    visited =[[False]*M for _ in range(N)] 
    BFS(graph, N,M, visited)
    print(graph[N-1][M-1])

if __name__=="__main__":
    main()