[이것이 취업을 위한 코딩테스트다] 05. DFS|BFS

1. 음료수 얼려 먹기(DFS)

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
ice=[list(map(int,list(input().rstrip()))) for _ in range(n)]

def dfs(x,y):
    if x<=-1 or y<=-1 or x>=n or y>=m:
        return
    if ice[x][y]==0:
        ice[x][y]=1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
    return False

count=0
for i in range(n):
    for j in range(m):
        if dfs(i,j)==True:
            count+=1
print(count)

 

2. 미로 탈출(BFS)

import sys
input=sys.stdin.readline
from collections import deque

n,m=map(int,input().split())
monster_map=[list(map(int,list(input().rstrip()))) for _ in range(n)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]

def bfs(x,y):
    queue=deque([(x,y)])
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if monster_map[nx][ny]==0:
                continue
            if monster_map[nx][ny]==1:
                monster_map[nx][ny]=monster_map[x][y]+1
                queue.append((nx,ny))
    return monster_map[n-1][m-1]
                    
print(bfs(0,0))