[알고리즘 이론] DFS, BFS (2)

1편은 아래 링크로!

https://jyoonit.tistory.com/28

[알고리즘 이론] DFS, BFS (1)

 

✅예제 : 음료수 얼려먹기

n * m 크기의 얼음틀. 0은 구명이 뚫려있는 부분, 1은 칸막이가 존재하는 부분. 구멍이 뚫려있는 부분끼리 상하좌우로 붙어있으면 연결되어 있다고 간주. 얼음 틀의 모양이 주어질 때 만들어지는 얼음의 개수?

 

💡내 풀이

n, m = map(int, input().split())
icetray = list()
for i in range(n):
    icetray.append(list(map(int, input())))

ice = 0

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

for x in range(n):
    for y in range(m):
        if icetray[x][y] == 0 :
            dfs(x, y)
            ice += 1
print(ice)

 

✅예제 : 미로 탈출

n * m 크기의 직하각형 형태의 미로에 갇혀있다. 미로에는 여러 마리의 괴물이 있어 피해서 탈출해야함. 현재위치는 (1, 1)이고 미로의 출구는 (n, m)의 위치에 존재. 괴물이 있는 부분은 0 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출가능한 형태로 제시됨. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. (시작칸과 마지막 칸을 포함함)

from collections import deque

n, m = map(int, input().split())
maze = []
for i in range(n):
    maze.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque()
    queue.append((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 maze[nx][ny] == 0:
                continue
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))
    return maze[n - 1][m - 1]

print(bfs(0, 0))

답안예시와 같은 코드...!! 어떻게 해야할지 모르겠어서 따라쳤당....ㅎ-ㅎ 다시 천천히 보면서 이해해봐야겠다

알고리즘어카냐....코테어쩜좋아...^^/