[KAKAO] 경주로 건설 (2020 KAKAO 인턴십)

주로 프로그래머스에서 문제를 풀게되면 카카오 관련 문제들이 많다. level 2부터 계속 풀어 왔지만, 다른 문제들보다 유난히

구현이 어렵고 문제 읽는 양 자체가 많았다.

 

좋은 문제들이 참 많다고 생각 했고, 어떤 응용 문제들이 많이 나오는지 정리하기 위해 KAKAO 카테고리를 따로 놨다.

level2 문제들이 구현에 치중된것이라고 본다면, level3 부터는 기본적인 알고리즘이 동반되어야 풀 수 있고, 어느정도의

센스가 필수적이라 생각한다. (개인적으로 센스는 문제들을 많이 풀어보고 디버깅을 해봄으로써 는다고 생각한다.)

 

미리 풀었던 문제들도 있기에 그 문제들은 다시 풀어보면서 블로그에 정리할 생각이다. 우선, 경주로 건설을 보자.

 

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

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

위 문제를 보게되면 단순 BFS만으로는 풀기 어렵다고 느껴질 수 있다. 

 

첫번째로 직선 경주로를 만들다가 코너를 만드는 순간을 어떻게 알아 차릴 수 있을까? 가 중요하다고 생각하고,

 

두번째로 각 지점에서의 최단거리를 어떤식으로 최신화 해주며 채워나갈까?를 생각해야한다.

 

물론 풀이는 다른 사람과 다를 수 있지만 글쓴이는 이렇게 풀었다.

 

1. BFS로직 구현 시 queue 에 들어갈 것들은 (row, column, cost, direction) 즉 행, 열, 비용, 방향을 넣었다. 

기본 행과 열에서 현재의 경주로 건설 비용을 q에 넣어줬다.

현재 어느 방향(오, 아래, 왼, 위) 인지 0~3 까지 수를 넣어가며 어느방향에서 온 경로인지 나타냈고 직선경로에 있게 된다면

100원을 더 해주고, 코너를 만들어야 한다면 600원(500원 추가) 해서 해당 좌표와 비교해 주도록 했다.

 

2. 첫 출발점에서 시작할 때는 어디든 직선 경로이므로 주의 해줘야한다.

( 여기서도 주의할 점은 첫 출발점 주변에 벽이 있을 수 있으며 넣어줄 때 벽인지 아닌지 확인 작업이 필요하다.)

만약 무턱대고 둘 다 넣게 되면 테스트 케이스는 다 통과되나 채점에서 틀릴 수 있다.

ex) 0 1 0     0 0 0

      0 0 0     1 0 0 

      0 0 0     0 0 0 

 

def solution(board):
    answer = 0
    N = len(board)
    nr, nc = [0, 1, 0, -1], [1, 0, -1, 0]
    check = [[0 for i in range(N)] for j in range(N)]
    q = []
    
    
    def bfs():
        while q:
            r, c, d, s = q.pop(0)
            for i in range(4):
                dr, dc = r + nr[i], c + nc[i]
                if 0<=dr<N and 0<=dc<N and board[dr][dc] == 0:
                    if i % 2 != s % 2:
                        if check[dr][dc] == 0:
                            check[dr][dc] = d+600
                            q.append((dr,dc,d+600, i))
                        elif d+600 <= check[dr][dc]:
                            check[dr][dc] = d+600
                            q.append((dr, dc, d+600, i))
                    else:
                        if check[dr][dc] == 0:
                            check[dr][dc] = d+100
                            q.append((dr,dc,d+100, i))
                        elif d+100 <= check[dr][dc]:
                            check[dr][dc] = d+100
                            q.append((dr,dc,d+100, i))
        return check[N-1][N-1]
    
    
    if board[0][1] == 0:
        check[0][1] = 100
        q.append((0,1,100, 0))
    if board[1][0] == 0:
        check[1][0] = 100
        q.append((1,0,100,1))
    answer = bfs()
    return answer