[ 백준 ] 1857 발레리노 ( Python )
안녕하세요! 오늘은 백준 온라인 저지에 있는 “발레리노” 문제를 파이썬을 사용하여 풀어보도록 하겠습니다. 이 문제는 그래프 탐색 알고리즘을 활용하는 문제로, BFS(너비 우선 탐색)를 사용하여 해결할 수 있습니다.
먼저, 문제를 자세히 읽어보면서 어떤 접근 방법으로 풀어야 할지 고민해 보았습니다. 문제에서 주어진 격자판을 그래프로 모델링하고, 나이트의 이동 규칙에 따라 각 칸을 연결하는 것이 핵심입니다. 그리고 시작 위치에서 도착 위치까지의 최단 거리와 경로의 개수를 계산해야 합니다. 이는 전형적인 최단 경로 문제이며, BFS를 사용하면 효과적으로 해결할 수 있겠다는 생각이 들었습니다.
그래프를 생성하는 부분에서는 조금 고민이 되었습니다. 처음에는 모든 칸에 대해 나이트의 이동 규칙을 적용하여 간선을 추가했는데, 이렇게 하니 불필요한 간선이 많이 생겨서 시간 복잡도가 높아질 것 같았습니다. 그래서 방석이 없는 칸이거나 시작/도착 위치가 아닌 경우에만 그래프에 추가하도록 수정했습니다.
BFS 탐색 과정에서는 최단 거리와 경로의 개수를 동시에 계산해야 해서 약간의 어려움이 있었습니다. 각각의 값을 별도의 리스트에 저장하고, 큐에서 정점을 꺼낼 때마다 이전 정점의 값을 이용하여 갱신하는 방식으로 해결할 수 있었습니다.
그럼 이제 문제 해결 과정을 단계별로 자세히 살펴보겠습니다.
Step 1: 입력 처리
- 격자판의 크기
n과m을 입력받습니다. - 격자판의 정보를
ipf리스트에 저장합니다. 이때 시작 위치(stx,sty)와 도착 위치(edx,edy)의 좌표도 찾아서 저장합니다.
Step 2: 그래프 생성
ipg리스트를 사용하여 각 칸에서 나이트의 이동 규칙에 따라 도달할 수 있는 칸들을 연결하는 그래프를 생성합니다.regg함수를 재귀적으로 호출하여 현재 칸에서 도달할 수 있는 칸들을 탐색합니다.- 현재 칸이 방석이 없는 칸이거나 시작/도착 위치가 아닌 경우에만 그래프에 추가합니다.
- 나이트의 이동 규칙에 따라 8가지 방향으로 이동할 수 있는 칸을 확인하고, 범위를 벗어나지 않는 칸에 대해 재귀 호출을 진행합니다.
Step 3: BFS 탐색
- 시작 위치에서 BFS 탐색을 시작합니다.
ipd리스트를 사용하여 각 칸까지의 최단 거리를 저장하고,ips리스트를 사용하여 각 칸까지 도달하는 경로의 개수를 저장합니다.- 큐(
ipq)를 사용하여 BFS 탐색을 진행합니다.- 큐에서 정점을 꺼내고, 해당 정점에서 도달할 수 있는 인접한 정점들을 확인합니다.
- 인접한 정점을 방문하지 않았다면, 최단 거리와 경로의 개수를 갱신하고 큐에 추가합니다.
- 이미 방문한 정점이라면, 최단 거리가 같은 경우에만 경로의 개수를 累加합니다.
Step 4: 결과 출력
- 도착 위치까지의 최단 거리가 0인 경우, 도달할 수 없는 경우이므로 “-1”을 출력합니다.
- 도달 가능한 경우, 최단 거리에서 2를 뺀 값을 출력합니다. (시작 위치와 도착 위치에는 이미 방석이 있기 때문)
- 도착 위치까지의 경로의 개수를 출력합니다.
이렇게 BFS 알고리즘을 활용하여 “발레리노” 문제를 해결할 수 있습니다. 그래프 탐색 알고리즘을 실전에 적용하면서, 최단 경로와 경로의 개수를 동시에 계산하는 방법을 배울 수 있었습니다.
특히 그래프를 생성하는 과정에서 불필요한 간선을 제거하여 효율성을 높이는 테크닉과, BFS 탐색 중에 최단 거리와 경로의 개수를 별도의 리스트에 저장하고 갱신하는 방법 등 유용한 테크닉들을 익힐 수 있었습니다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
ipf = []
ipg = [[[] for * in range(33)] for * in range(33)]
ipd = [[0] * 33 for _ in range(33)]
ips = [[0] * 33 for _ in range(33)]
imr = [[2, -1], [2, 1], [-2, -1], [-2, 1], [1, -2], [-1, -2], [-1, 2], [1, 2]]
for i in range(n):
row = list(map(int, input().split()))
ipf.append(row)
for j in range(m):
if row[j] == 3:
stx, sty = i, j
elif row[j] == 4:
edx, edy = i, j
def regg(st, ed, psx, psy):
ivs[psx][psy] = 1
if ipf[psx][psy] == 2:
return
if ipf[psx][psy] != 1 and not (psx == st and psy == ed):
ipg[st][ed].append((psx, psy))
return
for dx, dy in imr:
ntx, nty = psx + dx, psy + dy
if 0 <= ntx < n and 0 <= nty < m and ivs[ntx][nty] == 0:
regg(st, ed, ntx, nty)
for i in range(n):
for j in range(m):
ivs = [[0] * 33 for _ in range(33)]
regg(i, j, i, j)
ipq = deque([(stx, sty)])
ipd[stx][sty] = 1
ips[stx][sty] = 1
while ipq:
x, y = ipq.popleft()
for nx, ny in ipg[x][y]:
if ipd[nx][ny] == 0:
ipd[nx][ny] = ipd[x][y] + 1
ips[nx][ny] = ips[x][y]
ipq.append((nx, ny))
elif ipd[nx][ny] == ipd[x][y] + 1:
ips[nx][ny] += ips[x][y]
if ipd[edx][edy] == 0:
print("-1")
else:
print(ipd[edx][edy] - 2)
print(ips[edx][edy])
문제 해결 능력을 키우기 위해서는 다양한 유형의 문제를 접하고, 알고리즘과 자료구조에 대한 이해도를 높이는 것이 중요합니다. 또한, 문제 해결 과정에서의 시행착오와 디버깅 경험도 실력 향상에 큰 도움이 될 것입니다.
앞으로도 꾸준히 문제를 풀어보면서 역량을 쌓아가시길 바랍니다. 긴 글 읽어주셔서 감사합니다!