위 링크에서 너비 우선 탐색(BFS) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다.
3. 너비 우선 탐색(DFS)
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
- 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
- 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
- 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.
- (주의!) 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
- BFS는 재귀적으로 동작하지 않는다.
- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
- 즉, 선입선출(FIFO) 원칙으로 탐색
- 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
- ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.
BFS 기본 예제
- 방문 여부를 저장하기위해 리스트를 다음과 같이 만든다. visited = [False] * N
- 인접한 노드 정보는 graph 변수에 리스트로 저장한다.
- collections 라이브러리의 deque 를 사용하여 구현한다.
- 제일 처음 방문하는 노드를 리스트로 deque에 넣으면서 생성한다. deque([start])
- 넣으면서 방문처리를 한다. visited[start] = True
- while문을 돌며 큐에서 원소를 뽑아서 해당 원소의 인접 노드를 방문한다.
- v = queue.popleft() # 뽑기
- for i in graph[v]: # 인접 노드 돌기
- if not visited[i]: # 방문하지 않은 인접노드 방문하기
- queue.append(i) # 인접노드 큐에 넣기
- visited[i] = True # 방문 처리하기
- if not visited[i]: # 방문하지 않은 인접노드 방문하기
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end = " ")
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False]*9
bfs(graph, 1, visited)
# 출력
1 2 3 8 7 4 5 6
2차원일 때
def dfs(x,y):
dq = deque([x,y])
visited[x][y] = True
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while dq:
x, y = dq.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 > nx or nx > N or 0 > ny and ny > N:
continue
if not visited[nx][ny] and graph[nx][ny]==1:
visited[nx][ny] = True
dq.append([nx,ny])
문제
(❌ 표시는 혼자 못푼 문제)
2023. 12. 05. 1일차(7)
1. 2644번 촌수계산 (실버2) 문제링크
문제 해석
부모와 자식 사이를 1촌으로 정의한다. 이로부터 사람들 간의 촌수를 계산한다. 예를 들어 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성해보자.
제한: 1초 128MB
입력
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
각 사람의 부모는 최대 한 명만 주어진다.
출력
입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.
코드
방문 여부를 확인해줘야한다. 아니면 무한 루프가 발생한다.
간선을 이동할 때마다 각 노드마다 촌수를 저장해줘야 한다.
입력에서 100번까지의 사람이 있다는 것을 주의 깊게 봐야한다. 간선은 100명의 사람이 다 나오지는 않는다.
34MB, 60ms
import sys
from collections import deque
def _input():
return sys.stdin.readline().strip()
def bfs(start, target):
dq = deque([start])
visited[start] = True
while dq:
v = dq.popleft()
# v 까지의 촌수
myValue = value[v]
# v에 연결되어있는 가족까지의 촌수
connectValue = myValue + 1
for k in graph[v]:
if k == target:
return connectValue
if not visited[k]:
visited[k] = True
value[k] = connectValue
dq.append(k)
return -1
N = int(_input())
graph = [[] for _ in range(101)]
value = [0] * 101
visited = [False] * 101
#계산해야하는 두사람의 번호
a, b = map(int, _input().split())
#관계의 수
m = int(_input())
for _ in range(m):
x, y = map(int, _input().split())
graph[x].append(y)
graph[y].append(x)
print(bfs(a, b))
이 문제의 포인트
* BFS, DFS 사용할 때 방문 여부를 확인해줘야한다. 아니면 생각지 못한 부분에서 무한 루프가 발생할 수 있다.
* 노드 번호의 값이 1부터 시작하므로 graph배열의 크기를 +1 해준다. ex) 1~100이면 graph[100+1]
2023. 12. 05. 1일차(8)
2. 1260번 DFS와 BFS (실버2) 문제링크
문제 해석
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력
방문할 수 있는 정점이 여러개일 경우 작은 것부터 방문
더이상 방문할 수 있는 점이 없는 경우에는 종료.
정점 번호는 1번~N번
제한: 2초 128MB
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
코드
34MB, 80ms
import sys
from collections import deque
def _input():
return sys.stdin.readline().strip()
def dfs(start):
print(start, end=" ")
visited[start] = True
for k in graph[start]:
if not visited[k]:
dfs(k)
def bfs(start):
dq = deque([start])
visited[start] = True
while dq:
v = dq.popleft()
print(v, end=" ")
for k in graph[v]:
if not visited[k]:
visited[k] = True
dq.append(k)
N, M, V = map(int, _input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
v1, v2 = map(int, _input().split())
graph[v1].append(v2)
graph[v2].append(v1)
# list 자체 정렬. 정점이 여러개 일 경우 작은 것 부터 방문하기 위함
for g in graph:
g.sort()
visited = [False] * (N+1)
dfs(V)
print()
visited = [False] * (N+1)
bfs(V)2023. 12. 05. 1일차(9)
3. 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)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
출력
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.
코드
import sys
from collections import deque
def _input():
return sys.stdin.readline().strip()
def bfs(x, y):
# 상하좌우 인접한 땅에 배추가 심어져있는지 확인한다.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dq = deque()
dq.append((x, y))
visited[x][y] = True
while dq:
x, y = dq.popleft()
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:
visited[nx][ny] = True
dq.append((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]:
bfs(i, j)
count += 1
print(count)
이 문제의 포인트
* deque에 좌표를 쌍으로 넣을때 deque([1,2]) 이렇게 넣는건 쌍으로 넣는게 아니라 원소 1, 원소 2 두개를 넣는것이다.
쌍을 넣으려면 deque([(1,2)]) 이렇게 해주자! 두개의 원소가 있는 튜플을 하나의 원소로 넣는 것이다.
deque([[1,2]]) 리스트를 하나의 원소로 넣을 수도 있다.
* bfs visited True로 설정할 때 주의 할점.
아래 코드처럼 큐에서 빼낼때 방문처리를 하는 것이아니라 큐에 넣을 때 바로 방문처리를 해줘야한다. 그래야 다른 곳에서 방문을 안한다.
#잘못된 코드임!!!
def bfs(x, y):
# 상하좌우 인접한 땅에 배추가 심어져있는지 확인한다.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dq = deque()
dq.append((x, y))
#visited[nx][ny] = True
while dq:
x, y = dq.popleft()
visited[x][y] = True #여기에 visited를 하면안됨!
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:
#visited[nx][ny] = True
dq.append((nx, ny))
추가 문제
4. 2178번 미로 탐색 (실버1) 문제링크
5. 7562번 나이트의 이동 (실버1) 문제링크
6. 2468번 안전 영역 (실버1) 문제링크
7. 2583번 영역 구하기 (실버1) 문제링크
8. 1697번 숨바꼭질 (실버1) 문제링크
9. 12851번 숨바꼭질 2 (골드5) 문제링크
10. 13549번 숨바꼭질 3 (골드5) 문제링크
11. 13913번 숨바꼭질 4 (골드5) 문제링크
12. 1743번 음식물 피하기 (골드5) 문제링크
13. 5014번 스타트링크 (골드5) 문제링크
14. 6593번 상범 빌딩 (골드5) 문제링크
15. 7576번 토마토 (골드5) 문제링크
16. 16234번 인구 이동 (골드5) 문제링크
17. 2206번 벽 부수고 이동하기 (골드4) 문제링크
18. 5427번 불 (골드4) 문제링크
19. 4179번 불! (골드4) 문제링크
20. 3055번 탈출1 (골드4) 문제링크
21. 16397번 탈출2 (골드4) 문제링크
22. 9019번 DSLR (골드4) 문제링크
23. 14867번 교환 (골드3) 문제링크
24. 1039번 물통 (골드3) 문제링크
25. 1525번 퍼즐 (골드1) 문제링크
26. 17071번 숨바꼭질 5 (플레5) 문제링크
27. 3197번 백조의 호수 (플레5) 문제링크
'알고리즘 문제풀이' 카테고리의 다른 글
| 동적계획법(DP) 문제 및 풀이 (Python) (0) | 2023.12.04 |
|---|---|
| 완전탐색(브루트포스) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 깊이 우선 탐색(DFS) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 그리디 알고리즘 문제 및 풀이 (Python) (2) | 2023.10.01 |
| 코테 준비를 위한 알고리즘 공부 순서 (0) | 2023.09.25 |