[ALGORITHM] 5. DFS/BFS

이것이 취업을 위한 코딩테스트다 python 문제 풀이

5-10. 음료수 얼려 먹기

#C5. DFS/BFS - 실전문제 '음료수 얼려 먹기'

import sys
put = sys.stdin.readline
n, m = map(int, put().split())
shape = []
for i in range(n):
    shape.append(list(map(int, put())))

def dfs(x, y):
    #범위 넘어가면 끝냄
    if x<=-1 or x>=n or y<=-1 or y>=m:
        return False    
    if shape[x][y] == 0:  
        #방문 처리      
        shape[x][y] = 1
        #상좌우하 재귀적 호출
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

# 모든 노드(위치)에 대해 음료수 채우기
result=0
for i in range(n):
    for j in range(m):
                # 현재 위치에서 DFS 수행
        if dfs(i,j) == True:
            result += 1

print(result)

 

5-11. 미로 탈출

#C5. DFS/BFS - 실전문제 '미로 탈출'

import sys
from collections import deque
put = sys.stdin.readline
n, m = map(int, put().split())
maze = []
for i in range(n):
    maze.append(list(map(int, put())))
dx = [0, -1, 1, 0] #상좌우하 #x y 안 나누면 대각선 방향으로 더해져서 dx dy 나눠야
dy = [1, 0, 0, -1] 

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 원소 하나 뽑음
        x, y = queue.popleft()
        # 네 방향으로 이동
        for i in range(4):
            a = x+dx[i]
            b = y+dy[i]
            # 영역 벗어나면 무시
            if a<0 or a>=n or b<0 or b>=m:
                continue
            # 괴물 있으면 무시
            if maze[a][b] == 0:
                continue
            # 해당 노드를 처음 방문하면 기록
            if maze[a][b] == 1:
                maze[a][b] = maze[x][y] + 1 #기존 거에 더해야함
                queue.append((a,b))
        # 가장 오른쪽 아래까지의 최단 거리 반환
    return maze[n-1][m-1] #(0,0)이 문제 상 (1,1)로 인식되니까 (n-1,m-1)이어야 문제 상 (n,m)

print(bfs(0,0))