[알고리즘] DFS&BFS - (3)

🔒 문제1 : 음료수 얼려 먹기

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

⌨ 입력

- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
- 두 번째 줄부터 N + 1 번째 줄 까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

🖨 출력

- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

📚 예제

Ex)

- 입력 예시

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

- 출력 예시

8

📌 풀이

- 내 풀이

이런 2차원 배열 문제는 항상 x축, y축 위치가 바껴서 헷갈리는 것이 힘들었다.

하지만 몇 번 해보니까 이제 좀 쉬워지는 것 같다.

나는 이런 문제를 풀 때 아래 그림 처럼 항상 행을 x축으로, 열을 y축으로 해놓고 푼다.

그리고 x와 y의 범위도 헷갈리지 않도록 적어 놓고 풀어준다.

그리고 나서 bfs코드를 작성 후 코드를 돌려주면 된다.

시작점이 딱히 없기 때문에 모든 지점을 다 돌아봐야하는데, 만약 graph와 visited 둘다 0인 지점을 발견하면 거기서 부터 BFS를 실시한다.

BFS를 실시하는 동안 이어진 0들의 visited가 다 1로 바뀌면서 연결되지 않은 시작점이 될 지점만 for문이 돌면서, ans에 더해지게 된다.

- 이코테 풀이

이코테 책에서는 DFS로 풀어놨다. 풀이 과정은 크게 3 과정으로 나뉜다.

1️⃣ 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0' 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2️⃣ 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
3️⃣ 1️⃣~2️⃣번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

🔑 python 코드

- 내 코드 (BFS)

# 음료수 얼려 먹기
from collections import deque
import sys
input = sys.stdin.readline
# 세로, 가로 길이 입력 받음
N, M = map(int, input().split())
# 그래프 입력 받음 (문자열로 들어와서 정수형으로 변환시키는 작업 필요)
graph = [[int(x) for x in list(input().strip())] for _ in range(N)]
# 방문한 노드 표시
visited = [[0 for _ in range(M)] for _ in range(N)]

# 너비우선탐색
def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    visited[a][b] = 1

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    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
            else:
                if(graph[nx][ny] == 0 and visited[nx][ny] == 0):
                    queue.append((nx, ny))
                    visited[nx][ny] = 1
# 답 저장할 변수
ans = 0

# 전체 배열 다 돌아봄
for i in range(N):
    for j in range(M):
        if(graph[i][j] == 0 and visited[i][j] == 0):
            bfs(i, j)
            ans += 1
# 답 출력
print(ans)

- 답안 코드 (DFS)

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return false
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        graph[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) # 정답 출력

🔒 문제2 : 미로 탈출

동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

⌨ 입력

- 첫째 줄에 두 정수 N, M (4 <= N,M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수 (0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

🖨 출력

- 첫째 줄에 최소 이동 칸의 개수를 출력한다.

📚 예제

Ex)

- 입력 예시

5 6
101010
111111
000001
111111
111111

- 출력 예시

10

📌 풀이

최단 거리를 구하는 문제이기 때문에, BFS를 이용했을 때 효과적으로 해결이 가능한 문제이다.

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.

그러므로, (0, 0) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.

특정 노드를 방문하면 그 이전 노드의 값에 1을 더한 값을 그 노드에 넣는다.

아래의 그림들이 미로와 BFS를 실시하고 나서 바뀐 노드의 값이다.

🔑 python 코드

- 내 코드

# 미로 탈출
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(N)]

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    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
            else:
                if(graph[nx][ny] == 1):
                    queue.append((nx, ny))
                    graph[nx][ny] += graph[x][y]

    return graph[N - 1][M - 1]

print(bfs(0, 0))

- 답안 코드

from collections import deque

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스 코드 구현
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 graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

# BFS를 수행한 결과 출력
print(bfs(0, 0))