99클럽 코테 스터디 17일차 TIL + DFS/BFS

오늘의 문제 - DFS/BFS

백준 2644 - 촌수계산

https://www.acmicpc.net/problem/2644

---

내 풀이 및 접근 방식

1. BFS 이용

촌수는 곧 간선의 개수와 같다. 본인과 간선으로 직접 연결되어 있는 모든 사람은 1촌이고, 이후 1촌으로부터 파생된 1촌은 2촌이 되고, 2촌에서 파생된 1촌은 3촌이 된다. 그 과정에서 가까운 노드부터 차례대로 탐색하는 BFS 방식이 떠올랐다.

from collections import deque
import sys

n = int(sys.stdin.readline())   # 사람 수
a, b = map(int, sys.stdin.readline().split()) 
m = int(sys.stdin.readline())   # 부모자식 관계 수

# 부모 자식 간 그래프
m_list = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    m_list[x].append(y)
    m_list[y].append(x)

visited = [False for _ in range(n+1)]	# 방문 처리

def bfs(n1, n2):
    cnt = 0 # 촌수
    visited[n1] = True	
    queue = deque([(n1, cnt)])
    
    while queue:
        node, cnt = queue.popleft()
        
        for cn in m_list[node]:			# node(사람)의 1촌 탐색
            if not visited[cn]:			# 방문 안 한 사람인 경우
            	visited[cn] = True		# 방문 처리
                queue.append((cn, cnt+1)) 	# 큐에 (사람번호, n1과의 촌수) 삽입
            
            if cn == n2:			# n2이면 촌수 반환하고 반복문 종료
            	return cnt+1

    return -1

print(bfs(a,b))

풀이

1. 입력 받은 부모 자식 관계를 바탕으로 이중 리스트를 이용한 그래프를 만든다.
   이때 부모 자식 관계는 양방향 간선으로 표현하기 위해 양쪽에다가 요소를 추가한다.
   예제 입력 1의 결과를 이중 리스트로 표현하면 아래와 같다.
   graph = [[], [2, 3], [1, 7, 8, 9], [1], [5, 6], [4], [4], [2], [2], [2]]
   이 때, 1의 1촌은 인덱스1 의 값으로 [2,3]이 되는 것이고, 2의 1촌은 인덱스2 값으로 [1, 7, 8, 9]가 되는 것이다.
2. bfs: n1과 n2의 촌수 계산
   - 먼저 n1과 cnt(n1과의 촌수= 0)를 나타내는 cnt를 큐에 넣고 n1은 방문처리한다.
   - 큐에서 가장 첫번째 요소인 사람을 pop하여 1촌을 탐색하고, 1촌 중에 방문하지 않은 사람의 경우에만 촌수를 1씩 더해서 큐에 삽입한다.
   - 만약 탐색하는 1촌 중에 n2를 발견하면 촌수를 반환한다.
   위와 같은 과정을 큐에 사람이 남아있을 때까지 반복한다. while 문이 종료될 때까지 촌수를 구하지 못한 경우에는 -1을 반환한다.

2. DFS 이용

이전에 풀었던 풀이를 보니까 DFS를 이용했었다.

import sys

n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

v = [False for _ in range(n+1)]

ans = -1
def dfs(t, cnt):
    global ans

    if t == b:
        ans = cnt

    for nt in graph[t]:
        if not v[nt]:
            v[nt] = True
            dfs(nt, cnt+1)

v[a] = True	# a 방문처리
dfs(a, 0)

if ans == -1:
    print(-1)
else:
    print(ans)

풀이

1. 입력 받은 부모 자식 관계를 바탕으로 이중 리스트를 이용한 그래프를 만든다.
2. dfs: n1과 n2의 촌수 계산
   bfs와 다른 부분은 1촌 탐색을 하고 큐에 넣는 것이 아니라 다시 dfs 함수를 호출한다.

---

회고

DFS(깊이 우선 탐색)

• 경로를 따라 깊이 들어가며 탐색하는 방식
• 재귀적 접근을 사용
• 백트래킹을 통해 모든 경로를 확인할 수 있다.
• 특정 경로를 찾거나, 경로의 끝에 도달하는 문제에 적합하다.
• 최단 경로를 찾는 데는 비효율적

BFS(너비 우선 탐색)

• 동일한 레밸의 노드를 먼저 탐색하는 방식
• 큐를 사용하고, 가장 가까운 노드부터 탐색을 확장해나간다.
• 최단 경로를 찾는 데 효율적
• 각 단계에서 현재 노드와 연결된 모든 노드를 검사하기 때문에 최단 경로 보장

백트래킹 개념

• 재귀적 탐색: 문제를 해결하기 위해 재귀적으로 탐색 수행
• 경로 포기: 특정 경로가 목표 상태에 도달할 수 없다고 판단되면, 해당 경로 포기하고 다른 경로 탐색
• 유망성 검사: 현재 경로가 목표 상태로 이어질 가능성이 있는지 검사하여, 유망하지 않은 경로는 일찍 포기

백트래킹 관련 예제 - N-Queens

N x N 체스판에 N개의 퀸을 서로 공격하지 못하도록 배치하는 문제

def is_safe(board, row, col, n):
    # Check this column on upper side
    for i in range(row):
        if board[i][col] == 1:
            return False

    # Check upper diagonal on left side
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # Check upper diagonal on right side
    for i, j in zip(range(row, -1, -1), range(col, n)):
        if board[i][j] == 1:
            return False

    return True

def solve_nqueens(board, row, n):
    if row >= n:
        return True

    for col in range(n):
        if is_safe(board, row, col, n):
            board[row][col] = 1
            if solve_nqueens(board, row + 1, n):
                return True
            board[row][col] = 0  # Backtrack

    return False

def print_board(board, n):
    for row in board:
        print(' '.join('Q' if x else '.' for x in row))
    print()

n = 4
board = [[0] * n for _ in range(n)]
if solve_nqueens(board, 0, n):
    print_board(board, n)
else:
    print("Solution does not exist")

 

N-Queens 예제 설명

1. is_safe 함수: 현재 위치에 퀸을 놓을 수 있는지 확인합니다.
2. solve_nqueens 함수: 재귀적으로 퀸을 놓고, 다음 행으로 이동하며 가능한 모든 배치를 시도합니다.
3. 백트래킹: 특정 위치에 퀸을 놓고, 그 결과가 실패하면 퀸을 제거하고 다음 위치를 시도합니다.