아이디어
https://tech.kakao.com/2020/07/01/2020-internship-test/
위의 카카오 해설을 해석해보면
최단 거리 문제(BFS)로 뼈대를 잡은 뒤,
변형 구조인 코너 개수 부분을 고려해주는 문제로 권하고 있다.
코너 개수를 고려하는 이유는, 코너의 개수에 따라 최적 비용이 달라지기 때문이다. (즉, 최단 거리로 도착하더라도 코너가 많다면 비용이 높아져서 정답이 되지 않을 수 있기 때문이다)
모든 코너 개수의 경우(코너0개, 코너1개, 코너2개, ... )에 대하여 BFS로 최단거리를 돌려보고 ( O(코너개수) * O(BFS) ) 정답을 찾으면 된다고 한다.
풀이 요령
꼭 위의 카카오 해설과 동일하게 풀 필요는 없지만 아이디어를 가져왔다.
카카오 해설과 같이 배열 구조를 4차원으로 사용했다(다른 풀이로는 진행한 방향 과 건설 비용 을 사용한 풀이도 있다. 원글). 즉, 현재 좌표 이외에도 도착하기 직전에 진행한 방향(수평, 수직만 사용), 현재까지 건설 비용 또는 현재까지 늘어난 코너의 개수 정보를 index로 사용하고 배열의 값으로 이동 거리 를 사용하는 방법이 있다. 카카오 해설과 다른 부분은, 내 경우에는 상하좌우를 모두 사용하지 않고, 수평/ 수직 정보만 기록했다는 점과, 이동거리는 반드시 물리적인 이동만 기록했다는 점이다. (풀이에서는 방향전환과 물리적인 이동 모두 이동거리 +1을 해주고 나중에 비용 계산에서 방향전환으로 늘어난 이동거리를 다시 감해주고 있다)
중요한 부분은 visit 처리인데, 여기서는 4차원 배열이기 때문에 visit처리가 가장 중요하다. 우선 일반적으로 v[new_corner][ny][nx][hvs[i]] 동일한 상태값이 있는 곳에 다시 방문하지 않는 것은 2차원 때와 같다. 하지만 여기서 문제는 빙빙 돌면서 코너가 추가되면 이전에 내가 방문했던 곳이라고 하더라도 코너가 늘었기 때문에 또 같은 곳을 돌면서 무한 루프가 생길 수 있다는 것이다.
이 부분을 처리하기 위해, 자신의 이동 경로를 queue에 들고 다닐 필요가 있다. 이 문제에서 가장 중요한 부분이다.
- 처음에 q에 아래와 같이 정보를 들고다니기로 한다.
q.extend([[0,0,0,0,[]],[0,0,0,1,[]]])두 개의 queue가 있는 것은 하나는 오른쪽, 하나는 아래쪽 방향으로 출발할 수 있기 때문이다. - 그 다음에
corner, y,x,hv, visit = q.popleft()이와 같이 pop을 꺼낼 때 visit으로 경로를 선언한다. - 그 후에 새로운 위치가 경로상에 있는지 확인하고
(ny,nx) in visit - 다시 queue에는 이처럼 넣어준다.
q.append([new_corner, ny,nx,hvs[i], visit+[(ny,nx)]])
혹은 다른 방식으로 배열을 구성해도 된다.
마지막으로 모든 코너와 도착 방향(왼쪽에서 오른쪽, 위쪽에서 아래쪽)에 대하여 종점에서 탐색하며 최소 값을 찾는다. 이 부분은 for문을 사용했다.
결론
이 문제의 포인트는 진행한 방향을 어떤 방식으로 자료구조에 집어넣을지를 확인할 수 있어야 한다는 점이 하나이고, 두 번째는 bfs의 탐색이 2차원에서만 이루어지는 것이 아니라 4차원으로 진행되기 때문에 visit처리를 적절하게 잘 해주어야 한다는 점이다.
개인적으로 정말 까다로운 문제였다. 문제의 접근을 구조적으로 하기 위해서 먼저 아무런 제약조건 없는 bfs로 코드를 한번 짠 다음에 제약조건을 추가한 상태로 다시 짜는 방식으로 접근했다. 한번에 문제를 풀려고하니 복잡성이 높아서 도저히 되지 않았기 때문이다.
rom collections import deque
def solution(board):
v = [[[[0]*2 for _ in range(len(board))] for _ in range(len(board))] for _ in range(len(board)**2+1)] # 코너의 상태(개수)에 대하여 가장 먼저 접근한다.
dy = [1,0,-1,0]
dx = [0,1,0,-1]
hvs = [1,0,1,0] # 1은 수직, 0은 수평이동
def bfs()->int:
q = deque()
q.extend([[0,0,0,0,[]],[0,0,0,1,[]]]) # 처음 시작은 오른쪽으로 아래로 두군데로 갈 수 있기 때문에 두 개의 queue로 시작한다.
v[0][0][0][0] = 1
v[0][0][0][1] = 1
while q:
corner, y,x,hv, visit = q.popleft()
for i in range(4):
# 수평 i = 1,3 , 수직 i = 0,2
ny = y + dy[i]
nx = x + dx[i]
new_corner = corner + 1 if hv != hvs[i] else corner
if ny < 0 or nx < 0 or ny >=len(board) or nx >= len(board) or v[new_corner][ny][nx][hvs[i]] or board[ny][nx] or (ny,nx) in visit: # 자신의 이동 경로상 방문한적이 있다면 진행하지 않는다.
continue
q.append([new_corner, ny,nx,hvs[i], visit+[(ny,nx)]])
v[new_corner][ny][nx][hvs[i]] = v[corner][y][x][hv] + 1 # 한칸 이동했으니까 거리를 더해줌.
return v # 도착점 기준 누적 거리
answer = bfs()
#모든 코너의 경우에 대하여 0이 아닌 경우가 기록되어 있다면(실제로 종점에 도착했다면) 가장 작은 값을 구한다.
cost = 10e+9
for corner in range(len(v)):
for i in range(2):
if v[corner][len(board) - 1][len(board) - 1][i] == 0:
continue
dist = v[corner][len(board) - 1][len(board) - 1][i] - 1 # 코너 수는 같은 두 가지 도착 방향에 대하여 모두 계산 해본다.
cost = min(cost, dist * 100 + corner * 500)
return cost