99클럽 코테 스터디 8일차 TIL + 오늘의 학습 키워드

- 오늘의 학습 키워드

#BFS#DFS#deque

 

- 문제

백준

1697번, 숨바꼭질

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

 

- 오늘의 회고

BFS, DFS 개념을 배우고 공부한지 여러 번인데 이제서야 이해가 되는 거 같다. 

깊이 우선 탐색은 왜 깊이 우선 탐색인지 BFS는 언제 써야 효율적인지 느꼈다. 

 

- 어떤 문제가 있었고, 나는 어떤 시도를 했는지 

문제를 풀기 전에 BFS 뼈대 암기를 했다. 

외운 코드에서는 queue.extend(graph[node])를 통해 리스트를 큐에 삽입했다. (graph도 dict형이었다)

하지만 실전 백준 문제에서는 튜플을 사용해야 하는데 extend로 하니깐 계속 에러가 났다. append로 바꿔야 했다. 

튜플을 사용한 이유는 depth 를 추적하기 위해서였다. 

import sys
from collections import deque

input_data = sys.stdin.readlines()

N,K = map(int,input_data[0].split())

def bfs(N,K):
	visited = []
	queue = deque([(N,0)])
	while queue:
		node, depth = queue.popleft()

		if node == K:
			return depth

		if node in visited:
			continue
			
		visited.append(node)

		if node + 1 <= 100000:
			queue.append((node + 1, depth + 1))
		if node - 1 >= 0:
			queue.append((node - 1, depth + 1))
		if node * 2 <= 100000:
			queue.append((node * 2, depth + 1))

	return -1

print(bfs(N,K))

 

- 무엇을 새롭게 알았는지

queue.extend 는 iterable의 요소를 개별적으로 추가한다 -> 리스트 확장, 튜플도 됨 

queue.append 는 리스트에 단일 요소를 추가한다. 다음 예시를 보면 정확하게 알 수 있다. 

[1, 2].append([3, 4]) → [1, 2, [3, 4]]

[1, 2].extend([3, 4]) → [1, 2, 3, 4]