아이디어 및 풀이
최소 비용에서 다익스트라와 bfs가 떠올랐다.
문제의 board는 간선이라는 개념이 적용되지 않으므로, 사용할 알고리즘은 BFS로 결정했다.
일반적인 BFS에서는 방문배열을 사용해서 방문 여부에 따라 큐에 다음 위치를 넣을지 결정한다.
하지만 이번 문제에서는 비용이 '키 포인트'이므로, 비용을 저장하는 dist 배열을 사용해야하고,
해당 비용을 비교해서 다음 위치를 큐에 넣을지를 결정해야 한다.
또한 중요한 것이 '코너'라는 개념이다. 코너는 비용이 500원 더 추가되므로 이를 비교하는 코드가 필요하다.
언제 코너인가?
- 아래로 이동 중: 다음에는 오른쪽 또는 왼쪽으로 이동
- 오른쪽 또는 왼쪽으로 이동 중: 다음에는 아래로 이동
코드
실패 코드
from collections import deque
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = int(1e9)
def solution(board):
def check(nx, ny):
if nx < 0 or nx >= n or ny < 0 or ny >= n: return False
if board[nx][ny] == 1: return False
return True
n = len(board)
dist = [[INF] * n for _ in range(n)]
def bfs(x, y):
q = deque([(x, y, -2)])
dist[0][0] = 0
while q:
x, y, prev_dir = q.popleft()
cost = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny):
if dx[i] != prev_dir: # 방향이 다르다면 = 코너라면
if prev_dir == -2:
cost = 100
else:
cost = 600
else: # 코너가 아니라면
if prev_dir == -2:
cost = 100
else:
cost = 100
if cost + dist[x][y] < dist[nx][ny]:
dist[nx][ny] = dist[x][y] + cost
q.append((nx, ny, dx[i])) # 큐에 추가한다.
bfs(0, 0)
return dist[n - 1][n - 1]테스트 1 〉 통과 (0.03ms, 10.3MB) 테스트 2 〉 통과 (0.03ms, 10.3MB) 테스트 3 〉 통과 (0.03ms, 10.3MB) 테스트 4 〉 통과 (0.04ms, 10.2MB) 테스트 5 〉 통과 (0.05ms, 10.4MB) 테스트 6 〉 통과 (0.51ms, 10.4MB) 테스트 7 〉 통과 (0.57ms, 10.3MB) 테스트 8 〉 통과 (0.27ms, 10.3MB) 테스트 9 〉 실패 (0.25ms, 10.3MB) 테스트 10 〉 통과 (0.54ms, 10.3MB) 테스트 11 〉 실패 (3.38ms, 10.3MB) 테스트 12 〉 통과 (1.44ms, 10.2MB) 테스트 13 〉 실패 (0.34ms, 10.2MB) 테스트 14 〉 실패 (0.24ms, 10.2MB) 테스트 15 〉 통과 (0.50ms, 10.3MB) 테스트 16 〉 통과 (0.89ms, 10.3MB) 테스트 17 〉 실패 (1.07ms, 10.1MB) 테스트 18 〉 실패 (1.39ms, 10.2MB) 테스트 19 〉 실패 (1.91ms, 10.3MB) 테스트 20 〉 실패 (1.81ms, 10.3MB) 테스트 21 〉 통과 (0.84ms, 10.4MB) 테스트 22 〉 통과 (0.08ms, 10.2MB) 테스트 23 〉 통과 (0.07ms, 10.2MB) 테스트 24 〉 통과 (0.09ms, 10.3MB) 테스트 25 〉 실패 (0.08ms, 10.2MB)정확성: 64.0
합계: 64.0 / 100.0+) 테스트케이스 2번 실패
성공 코드
from collections import deque
from pprint import pprint
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = int(1e9)
def solution(board):
def check(x, y):
if x < 0 or x >= n or y < 0 or y >= n: return False
if board[x][y] == 1: return False
return True
def bfs(_dir):
q = deque([(0, 0, 0, _dir)])
dist = [[INF] * n for _ in range(n)]
dist[0][0] = 0
while q:
x, y, c, prev_dir = q.popleft()
if x == n - 1 and y == n - 1:
continue
# 0: 상, 1: 하, 2: 좌, 3: 우
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny):
if prev_dir == i:
cost = c + 100
else:
cost = c + 600
if cost < dist[nx][ny]:
dist[nx][ny] = cost
q.append((nx, ny, cost, i)) # 큐에 추가한다.
return dist[-1][-1]
n = len(board)
answer = min(bfs(1), bfs(3))
return answer다른 사람의 코드를 참고했다.
처음 위치는 (0, 0)이므로 우리가 갈 수 있는 방향은 아래(하), 오른쪽(우)이다.
따라서, 아래로 먼저갈 때 bfs와 오른쪽으로 먼저갈 때 bfs를 모두 수행한 다음에 최소값을 답으로 설정한다.
그리고 중요한 부분이 새로운 비용을 계산하는 코드이다.
아직 정확히 이해하지는 못했는데, dist[nx][ny]를 사용하게 되면 계속해서 테스트케이스2가 틀린다. 그래서 deque에 cost를 넣어서 해당 cost를 빼내와서(popleft()) 사용해야 한다.
추가로 bfs를 호출할 때, 나는 bfs(1), bfs(3)으로 호출했다.
위에서 언급했듯이 초기에 이동가능한 방향은 아래, 오른쪽이고 각 방향을 의미하는 dx, dy 리스트를 상, 하, 좌, 우 순서로 초기화했기 때문이다.
각 방향의 인덱스는 상: 0, 하: 1, 좌: 2, 우: 3이기 때문에 1과 3을 인자로 넣어서 bfs를 호출한 것이다.
그림을 그려봤을 때 어찌저찌 흐름은 이해하겠는데 정확히 왜 cost를 큐에 넣어야하는지는 다시 살펴봐야겠다.
큰 알고리즘은 떠올렸는데 세부 알고리즘을 떠올리지 못한게 아쉽다.
