코드 동작 및 알고리즘 설명
1. 최단 경로 탐색 (firstRoute 함수)
카드 선택 과정에서 커서 이동은 매우 중요합니다.
이동은 두 가지 방식으로 가능하는데, 한 칸씩 이동하는 방법과 Ctrl+방향키를 이용해 한 번에 여러 칸 이동하는 방법입니다.
이를 위해 **BFS(너비 우선 탐색)**를 사용하여 현재 위치에서 목표 위치까지의 최소 이동 횟수를 구합니다.
1-1. 행 이동 (goRow)
- 목적: 현재 위치의 행에서 목표 행까지 이동할 때, 한 칸 이동과 Ctrl 이동(빈 칸 건너뛰기)을 모두 고려합니다.
- 동작 방식:
- 시작점에서 시작하여, 상하 두 방향(dir이 1 또는 -1)으로 인접한 칸으로 이동할 수 있는지 확인합니다.
- 또한, 연속된 빈 칸들을 뛰어넘어 카드가 있는 칸 또는 보드 끝까지 이동할 수 있도록 while문을 사용합니다.
- BFS를 사용해 모든 가능한 이동을 탐색한 후, 목표 행에 도달했을 때의 누적 이동 횟수를 반환합니다.
1-2. 열 이동 (goCol)
- 목적: 행 이동과 동일하게, 열 방향으로의 이동을 탐색합니다.
- 동작 방식:
- goRow와 유사한 로직으로 인접한 열 이동과 Ctrl 이동을 모두 고려하여 최소 이동 횟수를 계산합니다.
1-3. 행 우선 vs 열 우선
- firstRoute 함수는 위의 두 가지 이동 방식을 조합합니다.
- 행 우선 (rowFirst): 현재 위치에서 먼저 행 이동을 수행한 후 열 이동을 수행.
- 열 우선 (colFirst): 현재 위치에서 먼저 열 이동을 수행한 후 행 이동을 수행.
- 두 방식 중 더 적은 이동 횟수를 선택하여 반환합니다.
2. DFS와 백트래킹을 이용한 카드 제거 순서 탐색
모든 카드 제거 순서는 경우의 수가 많기 때문에, **DFS(깊이 우선 탐색)**를 이용하여 모든 순서를 탐색합니다.
2-1. DFS (dfs 함수)
- 인자:
- r, c: 현재 커서의 위치
- depth: 현재까지 제거한 카드 쌍의 개수
- move: 현재까지 소모한 이동 횟수
- 동작:
- 만약 모든 카드 쌍을 제거했다면(depth == taskMax), 현재 이동 횟수와 전역 최소값을 비교하여 갱신합니다.
- 아직 제거하지 않은 카드 번호를 순회하면서, 해당 카드 번호가 보드 상에서 두 개의 위치를 갖는 것을 찾습니다.
- np 변수:
- 보드 전체를 순회하여 해당 카드 번호와 일치하는 두 좌표를 리스트에 저장합니다.
- 이때, 두 카드의 위치를 저장한 후, 두 가지 제거 순서(첫 번째 카드를 먼저 선택하는 경우와 두 번째 카드부터 선택하는 경우)에 대해 각각 이동 횟수를 계산합니다.
- 계산된 이동 횟수에 카드 선택 시 엔터 입력 2회(각 카드마다)를 더해 총 이동 횟수를 구한 후, 더 짧은 경로를 선택하여 재귀적으로 DFS를 진행합니다.
2-2. 백트래킹
- 카드 제거 후에는 보드 상태와 **방문 여부(taskVisited)**를 원래 상태로 복원합니다.
- 이를 통해 다른 제거 순서의 경우를 정확하게 탐색할 수 있습니다.
3. 알고리즘 요약
- 최단 경로 계산 (BFS)
- firstRoute 함수 내에서 행 이동(goRow)과 열 이동(goCol)을 BFS로 수행하여 커서 이동의 최소 횟수를 구합니다.
- 모든 카드 제거 순서 탐색 (DFS)
- DFS를 사용해 아직 제거하지 않은 각 카드에 대해 두 위치(리스트 np)를 찾고,
- 두 가지 제거 순서에 따른 이동 횟수를 계산한 후, 더 적은 이동 비용을 갖는 순서대로 재귀 호출합니다.
- 백트래킹
- DFS의 각 단계마다 보드의 상태와 방문 여부를 복원하여 모든 경우의 수를 탐색합니다.
결론
이 코드는 BFS와 DFS를 결합하여 문제를 해결합니다.
BFS를 통해 커서 이동 시 최소 이동 횟수를 정확하게 계산하고, DFS와 백트래킹을 통해 모든 카드 제거 순서를 탐색하여 전체 이동 횟수의 최소값을 구합니다.
이러한 접근 방식은 제한된 보드 크기와 카드 개수로 인해 충분히 빠르게 동작하며, 다양한 경우의 수를 모두 고려할 수 있는 강력한 방법입니다.
이 글이 여러분이 문제를 풀고 이해하는 데 도움이 되길 바랍니다.
추가 질문이나 개선 사항이 있다면 댓글이나 문의를 남겨주세요!
import collections
import functools
def solution(board, r, c):
# 카드 간 최단 경로를 찾는 핵심 함수
def firstRoute(r, c, tr, tc):
# 행과 열 방향으로 최단 경로를 찾는 내부 함수들
def goRow(r, c, tr):
# 행 방향 이동 탐색
visited = list(map(lambda _: False, range(4)))
rq = collections.deque([])
rq.append((r, 0)) # 시작 위치와 초기 깊이
while rq and rq[0][0] != tr:
curR, depth = rq.popleft()
# 두 가지 이동 방식 탐색 (상하 방향)
for dir in [1, -1]:
# 1. 인접한 칸으로 이동
if 0 <= curR + dir < 4 and not visited[curR + dir]:
visited[curR + dir] = True
rq.append((curR + dir, depth + 1))
# 2. 연속된 빈 칸을 건너뛰며 이동
nr = curR
while 0 <= nr + dir < 4:
nr += dir
if board[nr][c] != 0: # 카드를 만나면 정지
break
# 새로운 위치 방문
if not visited[nr]:
visited[nr] = True
rq.append((nr, depth + 1))
return rq[0][1] # 최단 경로 깊이 반환
# 열 방향 이동 탐색
def goCol(c, r, tc):
cq = collections.deque([])
visited = list(map(lambda _: False, range(4)))
cq.append((c, 0))
while cq and cq[0][0] != tc:
curC, depth = cq.popleft()
for dir in [1, -1]:
# 1. 인접한 칸으로 이동
if 0 <= curC + dir < 4 and not visited[curC + dir]:
visited[curC + dir] = True
cq.append((curC + dir, depth + 1))
# 2. 연속된 빈 칸을 건너뛰며 이동
nc = curC
while 0 <= nc + dir < 4:
nc += dir
if board[r][nc] != 0: # 카드를 만나면 정지
break
# 새로운 위치 방문
if not visited[nc]:
visited[nc] = True
cq.append((nc, depth + 1))
return cq[0][1] # 최단 경로 깊이 반환
# 행 우선 vs 열 우선 경로 중 최단 경로 선택
rowFirst = goRow(r, c, tr) + goCol(c, tr, tc)
colFirst = goCol(c, r, tc) + goRow(r, tc, tr)
return min(rowFirst, colFirst)
# 보드의 최대 카드 번호 계산
taskMax = max(list(functools.reduce(lambda x,y: x + y, board, [])))
# 최소 이동 횟수 초기화 (큰 값으로 설정)
answer = 100_000_000
# 카드 방문 여부 추적 (이미 제거한 카드 번호는 True로 처리)
taskVisited = list(map(lambda x: False, range(taskMax)))
def dfs(r, c, depth, move):
nonlocal board, answer, taskVisited
# 모든 카드를 제거했다면 최소 이동 횟수 갱신
if depth == taskMax:
answer = min(move, answer)
return
# 아직 제거하지 않은 카드 탐색
for nextInd in range(taskMax):
if taskVisited[nextInd]:
continue
# 현재 카드 방문 표시
taskVisited[nextInd] = True
next = nextInd + 1
# 현재 카드의 두 위치 찾기
np = []
for row in range(4):
for col in range(4):
if board[row][col] == next:
np.append((row, col))
# 두 카드의 위치
v0r, v0c, v1r, v1c = np[0][0], np[0][1], np[1][0], np[1][1]
# 두 가지 카드 제거 순서 계산
# 1. 첫 번째 카드 -> 두 번째 카드
curMove0 = firstRoute(r, c, v0r, v0c) + firstRoute(v0r, v0c, v1r, v1c) + 2
# 2. 두 번째 카드 -> 첫 번째 카드
curMove1 = firstRoute(r, c, v1r, v1c) + firstRoute(v1r, v1c, v0r, v0c) + 2
# 카드 제거 (보드에서 0으로 표시)
board[v1r][v1c] = 0
board[v0r][v0c] = 0
# 더 짧은 경로로 재귀 탐색 (두 가지 경우 중 하나 선택)
if curMove0 < curMove1:
dfs(v1r, v1c, depth + 1, move + curMove0)
else:
dfs(v0r, v0c, depth + 1, move + curMove1)
# 백트래킹: 카드 복원 및 방문 해제
taskVisited[nextInd] = False
board[v1r][v1c] = next
board[v0r][v0c] = next
# 초기 커서 위치에서 DFS 시작
dfs(r, c, 0, 0)
return answer
'알고리즘' 카테고리의 다른 글
| [알고리즘] 도둑질 python(프로그래머스) (0) | 2025.02.13 |
|---|---|
| [알고리즘] 메뉴 리뉴얼 python (프로그래머스) (0) | 2025.02.12 |
| [알고리즘] 연구소3 python(boj 17142) (1) | 2024.11.15 |
| [알고리즘] 감시 python (백준 15683) (0) | 2024.11.14 |
| [알고리즘] [모의 SW 역량테스트] 미생물 격리 python(SWEA 5653) (1) | 2024.11.12 |
