프로그래머스 레벨3 - 카카오 2020인턴 경주로 건설

문제주소

programmers.co.kr/learn/courses/30/lessons/67259

내 풀이

answer = 10e9


def dfs(board, pos, n, cost_board):
    x, y = pos[0][0], pos[0][1]
    dir = pos[1]
    cost = pos[2]
    global answer
    # 종료조건
    # 끝지점 도착
    if pos[0] == (n, n):
        answer = min(answer, pos[2] * 100)
        return
    # cost 가 answer보다 커지는건 최솟값이 아니므로 종료
    if cost > answer:
        return
    # cost_board에 저장된 값이 지금 cost 보다 작다는 것은 이미 방문한 곳이고, 이미 최솟값이므로 종료
    if cost_board[x][y] < cost:
        return
    direction = [0, 1, 2, 3]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nd = direction[i]
        if board[nx][ny] == 0 :
            # 방향이 같은 경우
            if nd % 2 == dir % 2:
                curr = ((nx, ny), dir, cost + 1)
                cost_board[nx][ny] = min(cost_board[nx][ny],cost + 1) # 이렇게 min값으로 갱신
            # 방향이 다른 경우
            if nd % 2 != dir % 2:
                curr = ((nx, ny), nd, cost + 6)
                cost_board[nx][ny] = min(cost_board[nx][ny],cost + 6) # 이렇게 min값으로 갱신
            dfs(board, curr, n, cost_board)


def solution(board):
    n = len(board)
    new_board = [[1] * (n + 2) for _ in range(n + 2)]
    for i in range(n):
        for j in range(n):
            new_board[i + 1][j + 1] = board[i][j]
    #시작에서 오른쪽으로 가는경우, 아래로 가는경우 2가지 모두 진행
    start_s = ((1, 1), 1, 0)
    start_c = ((1, 1), 0, 0)
    cost_board = [[10e9] * (n + 2) for _ in range(n + 2)]
    dfs(new_board, start_s, n, cost_board)
    dfs(new_board, start_c, n, cost_board)
    return answer

우와... 너무 어려웠다. 처음에 bfs로 도전했다가 안되서 dfs로 도전했는데 뒤에 테스트케이스가 통과가 안되었다. 안되는 이유를 찾아가며, 사실 인터넷에서 다른 풀이도 좀 참고하며 개선해나갔다.

 

1. 첫번째문제

dfs 리턴을 해주는 방식이 안되서 global을 사용하여 값을 갱신해주는 방식으로 했다. 재귀를 사용하는게 아직 좀 어렵다. return dfs를 하게되면 끝까지 탐색이 안되고 종료되어 버려서 호출을 해주어야 answer 값까지 도달 가능했다.

 

2. 계속 참조하는 인자(board)의 값!

dfs에 인자로 들어가는 new_board, cost_board 등은 계속 참조되는 값이다! 처음에는 visited나 new_board에 그대로 방문처리를 하는 것으로 하려했는데 계속 참조되는 값이라 한번 등록하면 변경이 안되었다. 계속 값을 가지고 다니는데 루트별로 다르게 값을 가져야했다. 그래서 다음에 시도했던 것이 copy.deepcopy(new_board)로 매번 copy한 값을 넘겨주는 것이었다. 매번 객체생성이 되어서 시간이 너무 오래걸린다ㅠㅠㅠ visited[:]로 copy 해주는 값을 줄여보려고 했지만 여전히 매번 복사해서 값을 가지고 다니는 것은 문제가 있다ㅠㅠ

 

여기까지 하다가 계속 막혀서 결국 인터넷에서 다른 dfs 풀이를 참고했다. 나의 코드에 아이디어를 적용해보았다. cost_board를 만들어서 가장 최소 cost를 갱신해주는 방식으로 했다. 이경우, min 메소드를 cost를 갱신해주어야 했고, 재귀의 종료조건을 잘 설정해주어야 했다. visited를 사용하기 까다로워서 최소값을 갱신하며 가지고 다니게 했더니 드디어 통과가 되었다!! 🎉

다른 사람 풀이

BFS로 푼 방식이 많은 듯 싶다. 힌트를 보려다가 다익스트라로 푸는 경우도 있는 것 같은데.. 스터디하면서 다른 풀이를 좀 더 참고해 봐야겠다. 어렵다..😅

정리

DFS와 BFS를 더 공부해야겠다는 생각이 더더욱 들었다. BFS에서는 queue를 DFS는 재귀를 많이 사용하는 것 같다. 어떤 값을 넣어주고, visited를 어떻게 처리할 것인지, 어떻게 종료할 것인지가 중요하다. ⚡

 

특히 이 문제는 어떻게 인덱싱하여 값을 사용할 것인지가 중요한 듯 하다. 어떻게 값을 가져올 것인지, 종료조건을 어떻게 설정할 것인지! 잘 생각하자! 재귀를 사용하는 것은 계속 참조되는 값(특히 배열)과 종료조건!에 유의하자!✔