1260

날짜 : 2022. 10. 15

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

def dfs(node):
    visited[node] = True
    print(node, end=" ")

    for i in graph[node]:
        if visited[i] == False:
            dfs(i)

def bfs(node):
    queue = deque([node])
    visited[node] = True
    while queue:
        #큐에서 하나의 원소를 뽑아 출력 후 기준노드로 잡음
        t = queue.popleft()
        print(t, end=" ")
        # 아직 방문하지 않은 원소 삽입
        for i in graph[t]:
            if not visited[i]: # 방문하지 않았다면
                queue.append(i) # 큐에 추가
                visited[i] = True # 방문처리
    return

n, m, v = map(int, sys.stdin.readline().split()) # 정점의 개수, 간선의 개수, 시작 정점
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for i in range(m): # n이라고 썼더니 11%에서 틀렸음
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

for i in graph: # 연결노드 오름차순 정렬
    i.sort()
# print(graph) # 디버그

dfs(v)
print()
visited = [False] * (n+1) # 방문 초기화
bfs(v)

 

 

알게된 점

- DFS, BFS를 공부한 후 바로 백트래킹만 했더니 버릇이 이상하게 잡혔다.

- 그래서 구글링으로 다시 DFS, BFS를 공부했다.

- DFS는 곧바로 이해해서 풀 수 있었는데 BFS는 데크를 사용해서 풀이해야 한다는 것을 까먹고 삼천포로 빠졌다.

- 스택이나 큐를 모두 다 채워서 풀이하는 방식으로 해보려고 했지만 너무 비효율적이었고, 풀이 마지막엔 간선 입력에서 m이 아닌 n으로 적는 바람에 오답도 나왔다.

- 그래도 곧바로 풀이방식을 이해해서 다행인 것 같다.

 

 

참고 사이트

- https://velog.io/@hamfan524/백준-1260번-Python-파이썬

[백준] 1260번-(Python 파이썬) - Bfs, Dfs