Level 3 경주로 건설 <2020 카카오 인턴십> Python 3

https://programmers.co.kr/learn/courses/30/lessons/67259?language=python3 

코딩테스트 연습 - 경주로 건설

 

최종 풀이

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_경주로건설.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(board):
    MAX = len(board)*len(board)*600
    q = deque()
    visit = [[[MAX]*len(board) for _ in range(len(board))] for _ in range(4)]
    if board[0][1] == 0:
        visit[0][0][1] = 100
        q.append([1,0,0,100])
    if board[1][0] == 0:
        visit[1][1][0] = 100
        q.append([0,1,1,100])
    for i in range(4):
        visit[i][0][0] = 100
    while q:
        now_x, now_y, now_d, cost = q.popleft()
        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if 0<=nx<len(board) and 0<=ny<len(board):
                if board[ny][nx]: continue
                if i == now_d:
                    new_cost = cost + 100
                else:
                    new_cost = cost + 600
                if visit[i][ny][nx] > new_cost:
                    visit[i][ny][nx] = new_cost
                    q.append([nx, ny, i, new_cost])
    min_cost = MAX
    for i in range(4):
        if min_cost > visit[i][-1][-1]: min_cost = visit[i][-1][-1]
    return min_cost
    
def solution(board):
    return bfs(board)

---

풀이 과정

 각 위치에 도달하는 최소 비용을 메모이제이션하면서 완전 탐색을 진행하는 방식으로 문제를 풀 수 있다.

이 때, 가장 중요한 점은 각 방향에 대해 해당 위치의 최소 비용을 메모이제이션 해야 한다는 점이다. 이 부분을 간과하면 테스트케이스 25번을 통과 할 수 없다.(아래 오답 노트를 참고하면 왜인지 알 수 있다.)

 

from collections import deque
#0-우, 1-하, 2-좌, 3-상
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(board):
	#최대 비용 = 모든 칸에서 코너가 있는 경우로 적용
    MAX = len(board)*len(board)*600
    #모든 방향에 대하여 N*N에 도달하는 비용의 최솟값을 담을 리스트, visit[direction][y][x]
    visit = [[[MAX]*len(board) for _ in range(len(board))] for _ in range(4)]
    
    q = deque()
    #시작점으로부터 오른쪽에 있는 칸이 벽이 아닌 경우, (x, y) = (1, 0), direction = 0
    if board[0][1] == 0:
		#오른쪽 직선 도로에 도로를 설치하므로 비용 = 100원
        visit[0][0][1] = 100
        q.append([1,0,0,100])
        
    #시작점으로부터 아래쪽에 있는 칸이 벽이 아닌 경우, (x, y) = (0, 1), direction = 1
    if board[1][0] == 0:
    	#왼쪽 직선 도로에 도로를 설치하므로 비용 = 100원
        visit[1][1][0] = 100
        q.append([0,1,1,100])
    
    #(0, 0)에서의 4방향 모두 비용을 100원으로 초기화
    for i in range(4):
        visit[i][0][0] = 100
        
    while q:
        now_x, now_y, now_d, cost = q.popleft()
        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            #(nx, ny)가 board 범위 안에 있는 경우
            if 0<=nx<len(board) and 0<=ny<len(board):
            	#(nx, ny)가 벽인 경우, 무시한다
                if board[ny][nx]: continue
                #방향이 바뀌지 않은 경우, 직선 도로를 설치하므로 100원의 추가 비용 발생
                if i == now_d:
                    new_cost = cost + 100
                #방향이 바뀐 경우, 코너가 발생하므로 600원의 추가 비용이 발생
                else:
                    new_cost = cost + 600
                #현재 방향의 (nx, ny)까지 도달하는데 드는 이전 비용이 new_cost보다 큰 경우, new_cost 값으로 갱신하고 해당 위치부터 BFS 탐색을 이어나가기 위해 큐에 삽입한다
                if visit[i][ny][nx] > new_cost:
                    visit[i][ny][nx] = new_cost
                    q.append([nx, ny, i, new_cost])
    min_cost = MAX
    #4 방향으로 경주로 끝에 접근하는데 드는 비용 중 가장 작은 비용이 min_cost이다
    for i in range(4):
        if min_cost > visit[i][-1][-1]: min_cost = visit[i][-1][-1]
    return min_cost
    
def solution(board):
    return bfs(board)
#시간복잡도 = O(n^2), 공간복잡도 = O(n^2)

---

오답 노트

풀이시간 2시간 10분

 

1. DFS

 먼저, 깊이 우선 탐색을 통해 모든 경로를 구하여 작은 cost 값으로 answer를 갱신해 나가는 방식으로 풀어봤다. 그랬더니 6개의 테스트케이스에서 시간초과가 떴다. 아무래도 중복 경로를 계속 탐색하기 때문에 시간초과가 난 것으로 예상된다.

(BFS 풀이처럼 메모이제이션을 통해 DFS로 문제를 풀 수 있다고 한다. 추후에 풀어볼 예정이다.)

import sys
sys.setrecursionlimit(20000)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def dfs(x, y, d, cost, visit, board):
    global answer
    if x == len(board)-1 and y == len(board)-1:
        if answer == -1: answer = cost
        elif cost < answer: answer = cost
        return
    if answer != -1 and cost >= answer: return
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<len(board) and 0<=ny<len(board):
            if visit[ny][nx] == 0 and board[ny][nx] == 0:
                visit[ny][nx] = 1
                if i == d: dfs(nx, ny, i, cost+100, visit, board)    
                else: dfs(nx, ny, i, cost+600, visit, board)
                visit[ny][nx] = 0

def solution(board):
    global answer
    answer = -1
    visit = [[0]*len(board) for _ in range(len(board))]
    for i in range(2):
        x = dx[i]
        y = dy[i]
        if board[y][x] == 1: continue
        visit[0][0] = 1
        visit[y][x] = 1
        dfs(x, y, i, 100, visit, board)
        visit[0][0] = 0
        visit[y][x] = 0
    return answer

 

DFS 풀이 결과

 

2. BFS

 다시 BFS로 접근해봤다. N*N visit 배열을 통해 (x, y) 칸에 도달할 때 드는 비용의 최솟값을 갱신해 나가는 방식으로 구현했다. 그런데 25번 테스트에서 실패가 떴다. 왜인지 모르겠어서 한참 헤매다가 예외상황이 있다는 것을 알게 되었다.

• 입력 예제

00000000

10111110

10010000

11000111

11110000

11111110

11111110

11111110

-> 정답: 4500

 

 위 예제를 입력으로 돌려보니 정답은 4900이 나왔다. 직접 종이에 써가며 어떤 상황인지 파악해보니 항상 (x, y)에 도달하는 가장 작은 비용을 선택해야만 최소 비용으로 경로 설정이 가능한 경우가 아닐 수도 있다는 점이다.

즉, 최종 풀이에서처럼 다른 방향으로 (x, y)칸에 도착하는 비용을 체크해줘야 한다. 이 문제의 가장 핵심적인 부분인 것 같다!

from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(board):
    q = deque()
    visit = [[0]*len(board) for _ in range(len(board))]
    if board[0][1] == 0:
        visit[0][1] = 100
        q.append([1,0,0,100])
    if board[1][0] == 0:
        visit[1][0] = 100
        q.append([0,1,1,100])
    visit[0][0] = 100
    while q:
        now_x, now_y, now_d, cost = q.popleft()
        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if 0<=nx<len(board) and 0<=ny<len(board):
                if board[ny][nx]: continue
                if i == now_d:
                    new_cost = cost + 100
                else:
                    new_cost = cost + 600
                if visit[ny][nx] == 0:
                    visit[ny][nx] = new_cost
                    q.append([nx, ny, i, new_cost])
                else:
                    if visit[ny][nx] >= new_cost:
                        visit[ny][nx] = new_cost
                        q.append([nx, ny, i, new_cost])      
    return visit[-1][-1]
    
def solution(board):
    return bfs(board)

BFS 풀이 결과

---

참고

• 1. 키패드 누르기 -> https://hwayomingdlog.tistory.com/138

Level 1 키패드 누르기 <2020 카카오 인턴십> Python 3

• 2. 수식 최대화 -> 2021.09.02 - [코테 노트/프로그래머스] - Level 2 수식 최대화 <2020 카카오 인턴십> Python 3

Level 2 수식 최대화 <2020 카카오 인턴십> Python 3

• 3. 보석 쇼핑 -> https://hwayomingdlog.tistory.com/136

Level 3 보석 쇼핑 <2020 카카오 인턴십> Python 3

• 5. 동굴 탐험