백준 | DFS와 BFS (1260) | 파이썬(Python)

백준 | DFS와 BFS (1260) | 파이썬(Python)

반응형

| 문제 설명

2606번 문제와 마찬가지로 DFS, 혹은 BFS를 이해했다면 풀 수 있다.

2021.08.20 - [개발자 도전기/[프로그래머스] 알고리즘 연습] - 백준 | 바이러스 (2606) | 파이썬(Python)

고려해야 할 포인트

1. 방문할 수 있는 노드가 여러 개일 때, 번호가 작은 것부터 방문

2. 두 노드 사이에 여러 개의 간선이 있을 수 있다(중복 고려).

| 풀이 과정

문제에서 주어진 입력값 받을 변수 설정

N = 정점 개수

M = 간선 개수

V = 탐색 시작할 정점 번호

graph = 딕셔너리 형태로 key값에는 컴퓨터, value값에는 key값의 컴퓨터와 연결된 컴퓨터들 추가

노드들의 연결여부 판단 위해 visited 리스트 자료형 생성

출력해야 하는 결과물이 DFS, BFS이므로 두 함수 정의

대부분 문제를 인접행렬로 구현했길래 다른 방식으로 문제를 해결하고 싶어서 동기한테 막히는 부분을 물어보면서 풀이했다.

| 최종 코드

from collections import deque, defaultdict # 함수 정의 def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: visited[i] = True dfs(graph, i, visited) def bfs(graph, start, visited): que = deque([start]) visited[start] = True while que: v = que.popleft() print(v, end=' ') for i in graph[v]: if not visited[i]: que.append(i) visited[i] = True N, M, V = map(int, input().split()) # collections 모듈의 defaultdict 함수를 이용하여 딕셔너리의 value를 리스트로 default graph = defaultdict(list) # Key = 컴퓨터 번호, Value = Key 컴퓨터와 연결된 컴퓨터들 for _ in range(M): a, b = map(int, input().split()) # defaultdict로 value가 리스트로 되어있기 때문에 append()를 통해 원소 추가 graph[a].append(b) graph[b].append(a) # 작은 것부터 탐색해야 하므로 때문에 graph의 value 내 원소들 오름차순으로 정렬 for i in graph.keys(): graph[i] = sorted(set(graph[i])) # 각 노드가 방문된 정보를 리스트 자료형으로 표현(False: 미방문, True: 방문) visited = [False] * (N + 1) dfs(graph, V, visited) print() # bfs 탐색 위해 visited 초기화 visited = [False] * (N + 1) bfs(graph, V, visited)

풀이 중 실수 기록

작은 것부터 방문하는 것과 중복을 고려하지 못해서 테스트케이스에서 원하는 출력값을 얻지 못했었음 graph를 정렬하려고 하는데 딕셔너리와 리스트의 for문 활용을 다르게 해야 한다는 것을 몰랐음(사실 공부했었지만 다 까먹음... 딕셔너리를 자주 쓰지 않다보니 ㅠㅠ 기초부터 제대로 공부하자)

| 공부한 내용 정리

1. 딕셔너리 for문 활용

dic이 딕셔너리라고 했을 때, for i in dic 으로 하면 i값은 dic은 key값을 출력한다.

value값을 출력하고 싶다면,

for i in dic.values()

for i in dic.values() key, value 모두 출력하고 싶다면,

for i in dic.items()

(예시)

반응형

from http://dapsu-startup.tistory.com/48 by ccl(A) rewrite - 2021-08-20 02:00:19