[#4 kakao 2020 internship] 경주로 건설

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

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

[풀이]

BFS로 접근했다.

단, 2차원 map이 아니라 3차원 배열로 visit 과 price를 계산해야한다. (요즘 3차원 graph문제를 심심치않게 본다.)

 

처음에는 습관성 dictionary이용으로 조금 어설프게 짰다.

visit을 딕셔너리로 키가 좌표 value가 price와 현재 방향 str으로, 

price 또는 방향이 겹치지 않는지를 확인하는 방식

from collections import defaultdict
def solution(board):
    q=[[0,0,0]]
    N=len(board)
    #v=[[[0] for i in range(N)] for i in range(N)]
    v=defaultdict(list)
    p=[[[10000000]*4 for i in range(N)] for i in range(N)]
    v[str((0,0))]=[0,0]
    p[0][0]=[0,0,0,0]
    x=[1,-1,0,0]
    y=[0,0,-1,1]
    direction=[0,1,2,3]#d,u,l,r
    while q:
        cur=q.pop(0)
        for i in range(4):
            if cur[0]==0 and cur[1]==0:
                price=100
            elif cur[2]==0:
                if x[i]==1:
                    price=100
                elif x[i]==-1:
                    price=10000000
                else:
                    price=600
            elif cur[2]==1:
                if x[i]==-1:
                    price=100
                elif x[i]==1:
                    price=10000000
                else:
                    price=600
            elif cur[2]==2:
                if y[i]==-1:
                    price=100
                elif y[i]==1:
                    price=10000000
                else:
                    price=600
            else:
                if y[i]==1:
                    price=100
                elif y[i]==-1:
                    price=10000000
                else:
                    price=600                              
            next_x=cur[0]+x[i]
            next_y=cur[1]+y[i]
            
            if next_x>=0 and next_x<N and next_y>=0 and next_y<N:
                if board[next_x][next_y]==0:
                    p[next_x][next_y][i]=min(p[next_x][next_y][i],p[cur[0]][cur[1]][cur[2]]+price)
                    if (p[next_x][next_y][i],i) not in v[str((next_x,next_y))]:
                                #p[next_x][next_y][i]=min(p[next_x][next_y][i],p[cur[0]][cur[1]][cur[2]]+price)
                                v[str((next_x,next_y))].append((p[next_x][next_y][i],i))
                                q.append([next_x,next_y,direction[i]])

        
    
    answer = min(p[N-1][N-1])
    print(answer)
    return answer

 

이렇게 짜고, 찝찝하던 와중에 visit을 2차원 배열로 재 구성했다.

간단하게 visit의 값이 price로 들어가고, 이게 더 작거나 같을때만 다시 visit할 수 있도록하면 되는 간단한 방법.

def solution(board):
    q=[[0,0,0]]
    N=len(board)
    v=[[-1 for i in range(N)] for i in range(N)]
    #v=defaultdict(list)
    p=[[[10000000]*4 for i in range(N)] for i in range(N)]
    #v[str((0,0))]=[0,0]
    v[0][0]=0
    p[0][0]=[0,0,0,0]
    x=[1,-1,0,0]
    y=[0,0,-1,1]
    direction=[0,1,2,3]#d,u,l,r
    while q:
        cur=q.pop(0)
        for i in range(4):
            if cur[0]==0 and cur[1]==0:
                price=100
            elif cur[2]==0:
                if x[i]==1:
                    price=100
                elif x[i]==-1:
                    price=10000000
                else:
                    price=600
            elif cur[2]==1:
                if x[i]==-1:
                    price=100
                elif x[i]==1:
                    price=10000000
                else:
                    price=600
            elif cur[2]==2:
                if y[i]==-1:
                    price=100
                elif y[i]==1:
                    price=10000000
                else:
                    price=600
            else:
                if y[i]==1:
                    price=100
                elif y[i]==-1:
                    price=10000000
                else:
                    price=600                              
            next_x=cur[0]+x[i]
            next_y=cur[1]+y[i]
            
            if next_x>=0 and next_x<N and next_y>=0 and next_y<N:
                if board[next_x][next_y]==0:
                    new_c=p[cur[0]][cur[1]][cur[2]]+price
                    #p[next_x][next_y][i]=min(p[next_x][next_y][i],p[cur[0]][cur[1]][cur[2]]+price)
                    if v[next_x][next_y]==-1 or v[next_x][next_y]>=new_c:
                                p[next_x][next_y][i]=min(p[next_x][next_y][i],p[cur[0]][cur[1]][cur[2]]+price)
                                v[next_x][next_y]=p[next_x][next_y][i]
                                q.append([next_x,next_y,direction[i]])

        
    
    answer = min(p[N-1][N-1])
    print(answer)
    return answer