[Algorithm] D-14 DFS/BFS 문제

음료수 얼려먹기

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


def dfs(x, y):
    # 밖으로 나가는 경우
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 0이면 1로 방문 처리하고 상하좌우 재귀적으로 살펴봄
    if data[x][y] == 0:
        data[x][y] = 1
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        return True
    return False


result = 0
# 모든 노드 확인
for i in range(n):
    for j in range(m):
        # 재귀적으로 살피면서 0 (1)-> 0 (1)-> 0 (1)-> 1 return True
        if dfs(i, j) == True:
            result += 1

print(result)

책 코드 도움을 받아 풀었다

미로탈출

from collections import deque

n, m = map(int, input().split())
# 미로 맵
data = []
for i in range(n):
    data.append(list(map(int, input())))

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y):
    # 큐 deque 선언
    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 data[nx][ny] == 0:
                continue
            # 갈 수 잇는 경우
            if data[nx][ny] == 1:
                # 이전 1 -> 2 -> 3 이런식으로 이동하면서 얼만큼 이동했는지 구하기 위해 이전 좌표값을 더해줌
                # (1,1)=1 (1,2)=(1,1)+1=2 이런식으로
                data[nx][ny] = data[x][y] + 1
                # 갈 수 있는좌표 다시 큐에 더해줌
                queue.append((nx, ny))
    # 제일 마지막칸 값을 구함
    return data[n - 1][m - 1]


print(bfs(0, 0))

순열 사이클

복습시간 나에게 맡긴다...

어떤 문제일때 BFS쓰는지 DFS 쓰는지 그 부분이 가장 어려운것같다.