백준 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로 해결한 풀이입니다.

감사합니다.🐧🐧🐧