백준 2606 python [실버3]

https://www.acmicpc.net/problem/2606

파이썬으로 처음 풀어보는 백준 문제
많이 버벅였지만 그래도 검색해가며 해결!

BFS

import sys
from collections import deque

# with open("./data.txt", "r") as f:
#     input_data = f.read().splitlines()
    
input = sys.stdin.read
input_data = input().splitlines()


N = int(input_data[0])
M = int(input_data[1])
graph = [[] for i in range(N+1)]
visited = [False] * (N+1)

# 노드 서로 연결
for line in input_data[2:]:
    a,b=map(int, line.split())
    graph[a].append(b)
    graph[b].append(a)

visited[1] = True
cnt = 0

Q = deque([1])
while Q:
    c=Q.popleft()
    for i in graph[c]:
        if visited[i]!=True:
            Q.append(i)
            visited[i] = True
            cnt += 1

print(cnt)
          

감을 잡기 위해서 기타 블로그를 참고하였는데

특정 번호의 노드에 어떤 노드들이 연결돼있는지 알기 위해서

각 노드를 배열로 선언해주고 연결된 애들을 append 해준다.

그리고 큐를 돌면서 방문하지 않은 경우에만

카운트, 방문처리, 큐에 담아주는것을 반복한다.

이러면 완성

DFS (2025.01.24)

import sys

# with open("./data.txt", "r") as f:
#     def input():
#         return f.readline().strip()
    
def input():
    return sys.stdin.readline()

def dfs(node):
    visited[node] = True
    global cnt
    
    for e in maps[node]:
        if(visited[e] == False):
            cnt += 1
            dfs(e)


N = int(input())
K = int(input())
global cnt

maps = [[] for _ in range(N+1)]
visited = [False] * (N+1)
cnt = 0

# 노드 연결
for _ in range(K):
    a, b = map(int, input().split(" "))

    maps[a].append(b)
    maps[b].append(a)
    
dfs(1)
print(cnt)import sys

# with open("./data.txt", "r") as f:
#     def input():
#         return f.readline().strip()
    
def input():
    return sys.stdin.readline()

def dfs(node):
    visited[node] = True
    global cnt
    
    for e in maps[node]:
        if(visited[e] == False):
            cnt += 1
            dfs(e)


N = int(input())
K = int(input())
global cnt

maps = [[] for _ in range(N+1)]
visited = [False] * (N+1)
cnt = 0

# 노드 연결
for _ in range(K):
    a, b = map(int, input().split(" "))

    maps[a].append(b)
    maps[b].append(a)
    
dfs(1)
print(cnt)

BFS보다 더 로직이 간단해지는듯하다.