백준 BFS/DFS 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://www.acmicpc.net/problem/2606
[나의 풀이]
⌛ 소요 시간 27분
N = int(input())
M = int(input())
graph = { str(i+1):[] for i in range(N)}
visited = [False for _ in range(N+1)]
visited[0] = True
visited[1] = True
for _ in range(M):
k,v = map(int,input().split())
# 양방향
graph[str(k)].append(v)
graph[str(v)].append(k)
# 시작점
stack = ['1']
cnt = 0
while stack:
v = stack.pop()
for x in graph[v]:
if not visited[int(x)]:
visited[int(x)] = True
# 탐색하지 않은 노드 append
stack.append(str(x))
cnt += 1
# 탐색한 노드 초기화
graph[v] = []
print(cnt)
양방향 DFS/BFS 문제입니다. 그래프 탐색을 하되 양쪽 모두로 이동할 수 있는 형태로 최근에 풀어본 유형과 같아 어렵지 않게 구현할 수 있었습니다.🐦🐦🐦
양방향 간선을 구하기 위해 서로의 노드에 요소를 추가하는 것이 포인트이고 이번에는 stack구조를 통해 DFS로 해결하였습니다.
[다른사람의 풀이1]
n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화
visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
a,b=map(int,input().split())
graph[a]+=[b] # a에 b 연결
graph[b]+=[a] # b에 a 연결 -> 양방향
def dfs(v):
visited[v]=1
for nx in graph[v]:
if visited[nx]==0:
dfs(nx)
dfs(1)
print(sum(visited)-1)
같은 DFS를 활용한 풀이이지만 graph에 [노드1]과 같이 리스트안에 하나의 노드만 있는 형태와 재귀함수로 구현했다는 점이 달랐습니다.🐻🐻🐻
[다른 사람의 풀이2]
from collections import deque
n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화
visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
a,b=map(int,input().split())
graph[a]+=[b] # a에 b 연결
graph[b]+=[a] # b에 a 연결 -> 양방향
visited[1]=1 # 1번 컴퓨터부터 시작이니 방문 표시
Q=deque([1])
while Q:
c=Q.popleft()
for nx in graph[c]:
if visited[nx]==0:
Q.append(nx)
visited[nx]=1
print(sum(visited)-1)
유사하게 [노드1]로 그래프를 구현한 형태이며 queue 구조를 통해 BFS로 해결한 풀이입니다.
감사합니다.🐧🐧🐧