깊이 우선 탐색을 통해서 노드를 방문해준다. 노드를 방문해줄 때마다 방문 횟수를 1씩 증가시켜준다. 인덱스를 구별하기 쉽게 인덱스 0은 빈칸으로 비워두었다.
n = int(input())
connect = int(input())
graph = [[] for i in range(n+1)]
count = 0
def dfs(graph,start,visited):
global count
visited[start] = True
for i in graph[start]:
if not visited[i] :
dfs(graph,i,visited)
count+=1
for i in range(connect):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False] * (n+1)
dfs(graph,1,visited)
print(count)
연결 요소의 개수를 구하는 문제였다. 예제 입력 1에서는 1,2,5가 3개의 간선으로 연결되어 있고, 3,4,6이 2개의 간선으로 연결되어 있으므로 예제 입력 1의 연결 요소는 2개이다. 이처럼 깊이 우선 탐색을 통해서 정점을 방문해준다. 이때, 연결 요소를 구해야하므로 반복문을 통해서 주어진 모든 정점을 확인해준 후, 방문 처리가 되지 않을 때만 숫자를 세주면 된다.
import sys
sys.setrecursionlimit(10000)
n, m = map(int, sys.stdin.readline().split())
lst =[[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
count = 0
def dfs(start):
visited[start] = True
for i in lst[start]:
if not visited[i]:
dfs(i)
for _ in range(m):
a,b = map(int, sys.stdin.readline().split())
lst[a].append(b)
lst[b].append(a)
for j in range(1, len(visited)):
if not visited[j]:
dfs(j)
count+=1
print(count)
DFS와 BFS를 구현하는 문제였다.
from collections import deque
def dfs(graph,v,visited):
visited[v] = True
print(v, end= " ")
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
def bfs(graph,start,visited):
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
n,m,v = map(int,input().split())
graph = [[] for i in range(n+1)]
visited = [False]* (n+1)
for i in range(m):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(1, n+1):
graph[i].sort()
dfs(graph,v, visited)
visited = [False]* (n+1)
print()
bfs(graph,v,visited)
고민하는 데 오랜 시간이 걸리기도 하였고, DFS의 응용에서 처음 보는 유형이어서 타인의 풀이를 참고했다. DFS와 같은 개념이었지만, 간선을 통해 연결되는 것이 아닌 상하좌우, 대각선의 방향을 설정해주어야 했다. 또한 지도의 너비와 높이가 정해져 있기 때문에 지도의 범위에서 벗어나지 않도록 조건을 지정해주어야한다.
import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
dx = [1,1,-1,-1,1,-1,0,0]
dy = [0,1,0,1,-1,-1,1,-1]
graph[x][y] = 0
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:
dfs(nx,ny)
while True:
w, h = map(int, sys.stdin.readline().split())
if w == 0 and h == 0:
break
graph = []
count = 0
for i in range(h):
graph.append(list(map(int, sys.stdin.readline().split())))
for i in range(h):
for j in range(w):
if graph[i][j] == 1:
dfs(i,j)
count +=1
print(count)
깊이 우선 탐색을 통해서 노드를 방문 처리하는 과정이 동일하다. 하지만 각 노드의 부모를 구해주어야 한다. 각 노드의 부모는 방문 처리하기 전의 노드들이다. 재귀 함수를 통해서 방문되지 않는 노드를 도는 과정에서 0으로 초기화되어 있는 visited
리스트에 부모 노드를 담아준다.
import sys
sys.setrecursionlimit(10**9)
n = int(input())
graph = [[] for _ in range(n+1)]
def dfs(start):
for i in graph[start]:
if visited[i] == 0:
visited[i] = start ## 부모 노드를 담아주는 과정
dfs(i)
for i in range(n-1):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
visited = [0] * (n+1)
dfs(1)
for i in range(2,n+1):
print(visited[i])