03-2. DFS/BFS 문제풀이

'이것이 코딩 테스트다 with 파이썬(나동빈)' 책을 기반으로 작성한 글입니다.

---

📝문제1. 음료수 얼려먹기

- 문제

p.149 참고

- 과정

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

- 정답 코드💻

n, m = map(int, input().split())

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

# 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)

- 비교 분석📖

dfs, bfs 개념과 문제가 처음이라 일단 책의 코드를 보면서 이해하고 공부했다.

---

📝문제2. 미로 탈출

- 문제

p. 152 참고

- 과정

BFS를 이용했을 때 매우 효과적으로 해결할 수 있다. BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다. 그러므로 (1,1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. 특정 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.

예를 들어 만약 미로의 크기가 3X3이며 오른쪽과 같이 구성되어 있다고 가정해보자.

110
010
011

1. 맨 처음에 (1,1)의 위치에서 시작하며 (1,1)의 값은 항상 1이라고 문제에 언급되어 있다.
   1 1 0
   0 1 0
   0 1 1

2. (1,1) 좌표에서 상, 하, 좌, 우로 탐색을 진행하면 바로 옆 노드인 (1,2) 위치의 노드를 방문하게 되고 새롭게 방문하는 (1,2) 노드의 값을 2로 바꾸게 된다.
   1 2 0
   0 1 0
   0 1 1

3. 마찬가지로 BFS의를 계속 수행하면 결과적으로 다음과 같이 최단 경로의 값들이 1씩 증가하는 형태로 변경된다.
   1 2 0
   0 3 0
   0 4 5

- 정답 코드💻

from collections import deque

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

# 이동할 네 방향 정의(상, 하, 좌, 우)
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 graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n-1][m-1]

print(bfs(0, 0))

---

📝문제3. 백준 10451번(순열 사이클)

- 문제

https://www.acmicpc.net/problem/10451
1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면
와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해
로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력
각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

예제 입력
2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

예제 출력
3
7

- 나의 코드💻

t = int(input())
test = []
result = 0
n, m = 0, 0

def dfs(x):
    global test, n, m, result
    if test[x] <= 0 or test[x] >= n+1:
        return False
    
    if 


for _ in range(t):
    result = 0
    test = []

    n = int(input())
    for _ in range(n):
        test.append(list(map(int, input().split())))
    dfs(1)

- 정답 코드💻

from sys import stdin
input = stdin.readline

# 재귀로 현 숫자가 가리키는 다음 숫자 확인
def dfs(startNum, originNum):
    global cycle
    nextNum = A[startNum]   # 현 숫자가 가리키는 다음 숫자
    if check[nextNum]:      # 이미 방문했다면 사이클 이루는지 확인
        if nextNum == originNum:    
            cycle += 1      # 사이클 이룬 것이므로 +1
            return
    else:   				# 첫 방문이라면 방문 표시
        check[nextNum] = 1
        dfs(nextNum, originNum)     # 재귀로 다음 숫자 확인

# main
T = int(input())
for _ in range(T):
    N = int(input())
    A = [0] + list(map(int, input().split()))
    cycle = 0
    check = [0] * (N+1)             # 방문 표시
    for start in range(1, N+1):
        if check[start]:            # 이미 방문한 곳이면 탐색 X
            continue
        check[start] = 1            # 새로 탐색 시작
        dfs(start, start)           # 이동할 숫자와 사이클 확인용 시작한 숫자

    print(cycle)

- 비교 분석📖

dfs에서 재귀를 이용하는 방식이 좀 어려운 것 같다. from sys import stdin을 사용하는 것도 아직 미숙하다. 내일 관련 문법을 좀 더 찾아봐야겠다! 사실 코드에서 이해가지 않는 부분들이 몇몇 있는데 내일 다시 봐야지.. 쉬운 문제라고 해서 조금 당황,, 처음이니깐,,!!! 괜찮다,,,,,,!!

코드 출처 블로그
https://chelseashin.tistory.com/87

---

💨

언제 bfs를 사용하고, 언제 dfs를 사용하는지 잘 구분이 안간다. 여러 문제를 풀어봐야 감이 올 것 같다. 그리고 그 과정을 생각해내는 것도 아직 미숙한 것 같다.