옛날에 풀 때는 아마
현 위치에서 가장 가까운 것들을 탐색해갔다.
그러다가 마지막에 시간 얼마 안 남기고
이게 그리디 + 구현 문제가 아닌 완전탐색 문제라는 것을 알아버렸다.
시간이 없어서 못 푼 문제였다.
그렇다면 문제가 그리디가 아닌 완전탐색이라는 사실은 어떻게 알까
완전탐색인지 아는 방법
1. 입력의 크기가 수상하리만큼 작다
완전탐색 문제의 입력값은 크기가 작을 것이다.
완전탐색이란 보통 의 알고리즘이다.
한 선택에서 다른 선택지가 개가 생길 수 있고, 이 선택을 번 반복해야 하는 것이다.
여기서 값과 값이 작아야 시간 내에 문제를 해결할 수 있다.
이 문제에서 게임판의 크기는 4x4로 한정되어 있고
카드 종류도 최대 6개 밖에 주어지지 않는다.
이렇게 입력값의 크기가 유독 작으면
완전탐색임을 의심해 볼 수 있다.
2. 선택할 때마다 다음 선택해야 할 게 바뀐다
선택할 때마다 다음 선택지의 집합이 달라진다면 이는 십중팔구 그리디가 아니다.
그리디 알고리즘을 적용하려면 선택을 어떻게 다르게 하든 다음 내가 볼 것은 정해져 있어야 한다.
예를 들어 단속 카메라 문제의 경우
진출 시점으로 오름차순 정렬한 뒤
왼쪽에서 오른쪽으로 훑으면서 카메라 설치 여부를 판별하는 방식으로 풀 수 있다.
이 경우 내가 카메라를 설치하든 설치하지 않든
내가 다음에 볼 것은 바로 다음 진출 지점이므로 그리디 알고리즘을 적용할 수 있다.
하지만 이 문제를 보자.
2번 카드 세트를 뒤집으러 갈 때 3의 비용이 들 것으로 예상되고, 이게 가장 작다고 치자.
2번 카드 세트를 모두 뒤집은 다음 최소 7의 비용으로 3번 세트를 뒤집을 수도 있다.
그런데만약 3번, 2번을 뒤집는 데 드는 각각의 최소 비용이 4, 3이라면?
처음엔 2번을 뒤집는 게 좋은 선택처럼 보이지만
전체적으로 봤을 땐 3번을 뒤집고 2번을 뒤집는 게 이득이다.
결과는 같지만 그리디하게 지금 당장 가장 빠른 경로만을 찾다보니
미래의 이득을 간과하게 되는 것이다.
3. 2번이지만 1번은 아니라면...
그리디는 분명 아닌데 입력값은 그다지 작지 않을 수도 있다.
그렇다면 동적 계획법이나 이분 탐색 등을 생각해봐야 할 수 있다.
결론
이 문제는 완전탐색 문제이다.
왜냐하면 카드를 뒤집을 때마다 내가 다음 가야할 곳이 계속해서 바뀌기 때문이다.
또한 입력값도 작으니 확실히 완전탐색으로 풀 수 있는 것이다.
코드
from collections import deque, defaultdict
def solution(board, r, c):
def dfs(i, now_pos, cnt):
nonlocal answer
if i == len_card:
answer = min(answer, cnt)
return
for adj in range(len_card):
if not visited[adj]:
for j in range(2):
s1 = card_pos[cards[adj]][j]
s2 = card_pos[cards[adj]][j-1]
dist = get_min_dist(now_pos, s1) + get_min_dist(s1, s2) + 2
if cnt + dist < answer:
visited[adj] = True
dfs(i + 1, s2, cnt + dist)
visited[adj] = False
for py, px in card_pos[cards[adj]]:
board[py][px] = cards[adj]
def is_valid(i, j):
is_in = lambda x: 0 <= x < N
return is_in(i) and is_in(j)
def get_next_node(now_y, now_x):
for dy, dx in deltas:
adj_y, adj_x = now_y + dy, now_x + dx
if is_valid(adj_y, adj_x):
yield adj_y, adj_x
while True:
if not is_valid(adj_y, adj_x):
adj_y -= dy
adj_x -= dx
break
if board[adj_y][adj_x]:
break
adj_y += dy
adj_x += dx
yield adj_y, adj_x
def get_min_dist(start, end):
will_visit = deque([(start, 0)])
check = {start}
while will_visit:
(now_y, now_x), now_dist = will_visit.popleft()
if (now_y, now_x) == end:
board[now_y][now_x] = 0
return now_dist
for adj in get_next_node(now_y, now_x):
if adj not in check:
check.add(adj)
will_visit.append((adj, now_dist + 1))
def get_card_pos():
nonlocal card_pos
for i in range(4):
for j in range(4):
if board[i][j]:
card_pos[board[i][j]].append((i, j))
N = 4
deltas = [(-1, 0), (0, 1), (1, 0), (0, -1)]
answer = float("inf")
card_pos = defaultdict(list)
get_card_pos()
cards = list(card_pos.keys())
len_card = len(card_pos)
visited = [False for _ in range(len_card)]
dfs(0, (r, c), 0)
return answer이곳의 코드를 일부 참고하였다.
yield
yield는 변수를 늦게 반환한다. yield는 양보한다는 뜻이다.
어떤 함수가 리스트를 반환해야 한다고 치면
리스트에 append해서 마지막에 한꺼번에 반환하는 방식도 있지만,
append 대신 yield를 해서 반환값을 그때그때 받아보는 방식도 있다.
get_next_node는 yield를 쓴 함수이다.
이 함수는 원래 리스트를 반환하게 되어 있다. (혹은 get_min_dist 함수에 들어가서 그때그때 큐에 추가하거나)
하지만 yield를 써서 이를
for adj in get_next_node(now_y, now_x)에서처럼 하나씩 뽑아쓰듯 반환값을 사용할 수 있다.
알고리즘 풀 때는 사실 크게 사용할 일은 없을 것 같고
극한의 최적화를 해야 할 때 사용할 수 있을 것 같다.
아니면 코드가 좀 더 간편해지는 경우도 있다.
원래 get_next_node라는 함수는 없었고 BFS인 get_min_dist 안에 들어가 그때그때 큐에 추가해줬다.
그런데 이렇게 다음 노드 찾는 과정을 따로 함수로 빼니 코드가 더 보기 편해졌다.
다음에 리스트 반환하는 코드를 작성할 때 yield를 사용해보아야겠다.
