위 링크에서 깊이 우선 탐색(DFS) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다.
2. 깊이 우선 탐색(DFS)
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다른 가지(branch)로 넘어가기 전에 현재 가지(branch)에 연결되어있는 애들을 완벽하게 탐색하는 방법
- 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다
- 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다
DFS 기본 예제
- 방문 여부를 저장하기위해 리스트를 다음과 같이 만든다. visited = [False] * N
- 데이터는 graph 변수에 리스트로 저장한다.
- 현재 노드와 연결된 자식노드를 재귀적으로 방문한다.
1. 재귀
# DFS 메서드 정의
def dfs(graph, v, visited):
#현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 자식 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
dfs(graph, 1, visited)
2. for문 (stack 활용)
def dfs(graph, start):
visited = set() # 방문한 노드를 저장
stack = [start] # 스택 초기화 (시작 노드 추가)
while stack:
node = stack.pop() # 스택에서 노드를 꺼냄
if node not in visited:
visited.add(node) # 방문 처리
# 현재 노드의 인접 노드들 중 방문하지 않은 노드를 스택에 추가
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return visited
문제
(❌ 표시는 혼자 못푼 문제)
2023. 12. 06. 2일차(1)
1. 1012번 유기농 배추 (실버2) 문제링크
문제 해석
농약을 쓰지 않고 유기농 배추를 재배하려고한다.
해충 방지를 위해 배추 흰지렁이를 구입하려고한다.
이 지렁이는 배추근처에 서식하며 해충을 잡아먹으며 배추를 보호한다.
어떤 배추에 배추흰지렁이가 한마리라도 살고 있으면 이 지렁이는 인접한(상하좌우) 다른 배추로 이동이 가능한다. 그 배추들 역시 해충으로부터 보호됨.
배추들이 모여있는 곳에는 배추흰지렁이가 한마리 필요.
인접해있는 배추들이 몇군데 퍼져있는지 조사하여 총 몇마리의 지렁이가 필요한지 구해보자.
0: 배추가 심어져있지 않은 땅
1: 배추가 심어져 있는 땅
제한: 1초 512MB
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
출력
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.
코드
31MB, 56ms
import sys
sys.setrecursionlimit(10**6)
def _input():
return sys.stdin.readline().strip()
def dfs(x, y):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 상하좌우 인접한 땅에 배추가 심어져있는지 확인한다.
visited[x][y] = True
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 유효한 범위인 경우에만 실행
if -1 < nx < N and -1 < ny < M \
and not visited[nx][ny] and graph[nx][ny] == 1:
dfs(nx, ny)
case = int(_input())
for _ in range(case):
M, N, K = map(int, _input().split())
graph = [[0] * M for i in range(N)]
visited = [[False] * M for i in range(N)]
for i in range(K):
x, y = map(int, _input().split())
graph[y][x] = 1
count = 0
for i in range(N):
for j in range(M):
if graph[i][j] == 1 and not visited[i][j]:
dfs(i, j)
count += 1
print(count)
이 문제의 포인트
* RecursionError (참고)
- Python이 정한 최대 재귀 깊이: BOJ의 채점 서버에서 이 값은 1,000으로 되어 있다.
- 재귀를 사용하지 않거나 sys.setrecursionlimit(10**6) 코드로 최대 깊이를 1,000,000 정도로 크게 설정해 런타임에러 없이 실행할 수 있다.
- 최대 깊이 제한이 너무 작을 때도 RecursionError가 발생합니다.
- 최댓값을 크게 변경했다고 하더라도, 재귀의 깊이가 채점 서버가 감당할 수 없는 정도로 깊어지면, Segmentation fault가 발생해 런타임 에러 이유로 SegFault를 받게됩니다.
* 상하좌우를 확인할 때 dx, dy로 방향을 이동한다.
2023. 12. 06. 2일차(2)
2. 11724번 연결 요소의 개수 (실버2) 문제링크
문제 해석
방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 작성해보자.
제한: 3초 512MB
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
코드
800ms
import sys
sys.setrecursionlimit(10**6)
def _input():
return sys.stdin.readline().strip()
def dfs(i):
visited[i] = True
for k in graph[i]:
if not visited[k]:
dfs(k)
N, M = map(int, _input().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
for _ in range(M):
u, v = map(int, _input().split())
graph[u].append(v)
graph[v].append(u)
count = 0
for i in range(1, N + 1):
if not visited[i]:
dfs(i)
count += 1
print(count)2023. 12. 06. 2일차(3)
3. 11403번 경로 찾기 (실버1) 문제링크
문제 해석
가중치 없는 방향 그래프 G가 있다.
모든 정점 (i, j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하여라.
제한: 1초 256MB
입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
코드
i 에서 j로 갈수 있는 경로가 존재하는지 확인하는 것. 경로가 존재하면 i,j 행렬에 1을 출력하면된다.
i == j 같을 경우도 확인해줘야 하기 때문에 처음 시작하는 i는 방문안하고 시작한다. 나중에 방문할 수 있어야 i->j 경로가 확인되기 때문 (BFS로 푼것)
34MB, 120ms
import sys
from collections import deque
def _input():
return sys.stdin.readline().strip()
def bfs(start, target):
dq = deque([start])
visited = [False] * (N + 1)
while dq:
x = dq.popleft()
for k in graph[x]:
if k == target:
return 1
if not visited[k]:
visited[k] = True
dq.append(k)
return 0
N = int(_input())
graph = [[] for _ in range(N)]
result = [[0] * N for _ in range(N)]
for i in range(N):
arr = list(map(int, _input().split()))
for j in range(N):
if arr[j] == 1:
graph[i].append(j)
#i->j 결과를 dfs 한번으로 반환받는다.
for i in range(N):
for j in range(N):
result[i][j] = bfs(i, j)
for i in range(N):
for j in range(N):
print(result[i][j], end=" ")
print()
이 문제의 포인트
* deque는 리스트등과 같이 iterable 기반의 데이터를 인자로 받아서 deque 생성이 가능. deque([1,2]) or deque('love') or deque([])
* 재귀를 사용하지 않은 dfs이다.
추가문제
'알고리즘 문제풀이' 카테고리의 다른 글
| 동적계획법(DP) 문제 및 풀이 (Python) (0) | 2023.12.04 |
|---|---|
| 완전탐색(브루트포스) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 너비 우선 탐색(BFS) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 그리디 알고리즘 문제 및 풀이 (Python) (2) | 2023.10.01 |
| 코테 준비를 위한 알고리즘 공부 순서 (0) | 2023.09.25 |