[백준] 2667번: 단지번호 붙이기 Python 풀이문제 백준 2667번 단지번호붙이기 문제입니다.그래프를 탐색하는 문제이므로 BFS / DFS를 이용해서 풀 수 있습니다.DFS이 문제는 DFS / BFS 어느 것을 선택해도 풀 수 있습니다. 출력은 단지의 수와 단지 내 집의 수를 출력해야 하므로 Dictionary 내부에 저장하겠습니다.result = dict()# 예상 구조# 1번 단지 : 10# 2번 단지 : 5# ... 그래프를 $(0,0)$ 부터 $(n-1, n-1)$까지 순회하며 집$(1)$에 해당하는 값을 찾습니다.// 그래프 순회for i in range(n) : for j in range(n) : 집을 찾았다면 그 자리에서 DFS / BFS 탐색을 수행합니다.이때 대각선은 고려하지..

[백준] 2178번: 미로 탐색 Python 풀이문제 백준 2178번 미로 탐색 문제입니다.(1,1)에서 (N, M)까지 최소 거리를 구하는 문제이므로 BFS를 이용해서 풀 수 있습니다.BFS타일형 문제는 BFS로 풀 경우, 각 타일마다 이동할 수 있는 방향을 모두 계산하여다음 타일이 조건에 부합한다면 Queue에 저장합니다. 문제에서는 적혀있지 않지만 4방향으로만 움직일 수 있기 때문에 이동 방향을 정해줍니다.moves = [[0,1], [0,-1], [1,0], [-1,0]] 시작 위치는 (1,1)로 고정되어 있으니 해당 값을 Queue에 넣습니다.Python 리스트는 0부터 시작하므로 [0,0]을 넣어줍니다. 각 타일에서 갈 수 있는 다음 타일의 경우를 구한 뒤, 몇 가지 조건을 검사합니다.다음 타..

[백준] 1697번 숨바꼭질 Python 풀이문제 백준 1697번 숨바꼭질 문제입니다. 이 문제를 처음 보았을 때는 DP로 풀어야겠다고 생각했습니다.특정 지점에서 역으로 최단거리를 구하면 가볍게 DP로 풀 수 있을 거 같은데... DP로 풀어보기1. N >= K 일 때일단 문제를 잘 살펴보면 $ 0$ N 그런데 뒤로 가는 방법은 X-1 의 경우 밖에 없으니 $ N >= K $ 일 때 답은 $ N - K $입니다. 2. N DP로 풀기 위해서는 점화식을 잘 세워야 합니다.일단 최소 거리를 구해야 하기 때문에 초기 값은 무한대로 설정하였습니다.역으로 생각했을 때, 특정 지점 $X$로 갈 수 있는 방법은 $X-1$에서 한 칸 앞으로, $X+1$에서 한 칸 뒤로,짝수일 때는 $X/2$ 에서 순간 이동하는 3가지..