[알고리즘/파이썬] 프로그래머스 - 경주로 건설

문제

https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

 

풀이

정말정말.. 생각보다 너무너무 오래걸린 문제..ㅠ

문제를 보자마자 내가 정말 애정.하는 bfs문제임을 알았고, 그냥 벽만 피해서 최소비용 구하면 되겠다! 하고 생각을 했다.

 

이 문제가 기본 bfs의 최소비용문제와 달랐던 점은 바로 '코너'비용을 계산하는 것이었는데, 나는 처음 시작때만 방향 값을 -1을 두어 따로 분기 처리를 해주었고, 그 뒤부터는 현재 좌표로 오기 이전에 (위-아래) 로 움직인것인지, (좌-우)로 움직인 것인지를 체크하여 기존의 이동방향과 방향이 바뀌었다면 코너비용500에 직진비용100을 더해 총 +600을 더해주고, 직진 했다면 직진비용 +100만 해주는 방식을 채택했다.

 

내가 쓴 코드에서 이 부분이 방향을 체크하고 비용을 더해주는 부분이다.

dx = [0,0,1,-1]
dy = [-1,1,0,0]
    
# 위,아래 = 0 / 왼,오 = 1
# 이전 d를 저장해두고 d가 바뀌면 코너가 생긴 것이므로 +500 해주기
d = [0,0,1,1]


# ... 중간 코드 생략 (전체 코드는 밑에 정답 코드에 있습니다)


# 첫 시작인 경우. 사실 x==0 and y==0 이런 식으로 분기 처리해줘도 상관 없다
if cd == -1:
	new_sum = c_sum + 100

# d[cd]는 이전에 움직인 방향이 (좌<->우)인지 (상<->하)인지를 나타내는 값이고
# d[i]는 현재 움직이고자 하는 nx,ny로 갈 경우 움직이는 방향이 (좌<->우)인지 (상<->하)인지를 나타내는 값이다.
# 만약 이 둘이 다른 값이라면 이전에 이동해온 방향과 현재 이동하고자 하는 방향이 다른 것이므로 == 코너가 생긴 것이므로
# + 600을 해줘야 한다
elif d[cd] != d[i]:
	new_sum = c_sum + 600
else:
	new_sum = c_sum + 100

 

자 그래서, 이 부분만 신경쓰고 일반적인 최소 비용 문제처럼 visited의 x,y좌표값에 최소값을 넣어준다면... 순조롭게 답을 구할 수 있을 거라고 생각했다.

 

첫 번째 시도

from collections import deque
def solution(board):
    answer = 1e9

    dx = [0,0,1,-1]
    dy = [-1,1,0,0]
    
    # 위,아래 = 0 / 왼,오 = 1
    # 이전 d를 저장해두고 d가 바뀌면 코너가 생긴 것이므로 +500 해주기
    d = [0,0,1,1]
    n = len(board)
    
    def bfs():
        nonlocal answer
        visited = [[1e9 for _ in range(n)] for _ in range(n)]
        visited[0][0] = 0
        q = deque()
        # x, y, 이전 이동 방향(처음엔 -1)
        q.append((0,0,-1))
        
        while q:
            x,y,cd = q.popleft()
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                # 범위를 벗어나거나 벽이라면 무시
                if nx<0 or ny<0 or nx>=n or ny>=n or board[nx][ny]==1:
                    continue
                    
                if cd == -1:
                    new_sum = visited[x][y] + 100
                elif cd != d[i]:
                    new_sum = visited[x][y] + 600
                else:
                    new_sum = visited[x][y] + 100
                
                # 지금 계산된 값보다 현재까지 발견된 최솟값이 더 작다면 무시
                if visited[nx][ny] < new_sum:
                    continue
                # 지금 발견된 값이 현재까지 발견된 최솟값보다 더 작다면 최솟값 갱신해주기
                visited[nx][ny] = new_sum
                q.append((nx,ny,d[i]))
                
        return visited[n-1][n-1]
    
    answer = bfs()
            
    return answer

이 코드의 정확도는 72퍼였다.

 

도저히 무엇이 문제인지 파악을 못하겠어서 질문게시판을 찾아보니 

https://school.programmers.co.kr/questions/58913

프로그래머스

이런 글이 있었다. 현재 당장은 최솟값보다 값이 클 수 있어도 그 뒤에 직진을 계속함으로써 최종적인 값은 더 작을 수 있다는 것이었다.

 

그래서 이 부분을 어떻게 고려해줄까 하다가

현재는 지금 당장의 값이 최솟값보다 크면 의미없다고 판단했지만

현재값-500(코너비용만큼) 보다 최솟값이 작으면 이 최솟값이 확실한 최솟값이라고 판단할 수 있을거라고 생각해서 그걸 기준값으로 판단해야겠다고 생각했다.

즉 

visited[nx][ny] < new_sum

 

이 조건을

visited[nx][ny] < new_sum-500

 

으로 바꿔주는 것이다! 그치만... 지금 다 풀고 이 500을 300으로 바꿔도 100점이 나온다. 음.ㅠ 너무 얻어걸려 맞춘것 같은데, 혹시 확실하게 아시는 분 있으면 댓글 부탁드립니다...

 

두 번째 시도

from collections import deque
def solution(board):
    answer = 1e9

    dx = [0,0,1,-1]
    dy = [-1,1,0,0]
    
    # 위,아래 = 0 / 왼,오 = 1
    # 이전 d를 저장해두고 d가 바뀌면 코너가 생긴 것이므로 +500 해주기
    d = [0,0,1,1]
    n = len(board)
    
    def bfs():
        nonlocal answer
        visited = [[1e9 for _ in range(n)] for _ in range(n)]
        visited[0][0] = 0
        q = deque()
        # x, y, 현재방향, 비용
        q.append((0,0,-1,0))
        
        while q:
            x,y,cd,c_sum = q.popleft()


            if x == n-1 and y==n-1:
                answer = min(c_sum,answer)
                continue
            
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if nx<0 or ny<0 or nx>=n or ny>=n or board[nx][ny]==1:
                    continue
                    
                if cd == -1:
                    new_sum = c_sum + 100
                elif d[cd] != d[i]:
                    new_sum = c_sum + 600
                else:
                    new_sum = c_sum + 100

                if (cd!=-1 and nx==x-dx[cd] and ny == y-dy[cd]) or visited[nx][ny] < new_sum - 500:
                    continue
                
                visited[nx][ny] = min(visited[nx][ny],new_sum)
                q.append((nx,ny,i,new_sum))

    
    bfs()
            
    return answer

 

암튼 그래서 이번엔 visited를 기준으로 계산하지 않고, visited의 값은 최소값을 저장해주고 비교, 갱신해주는 용도로만 사용하고, 현재까지의 비용은 q에 넣어서 관리해주는 식으로 변경했다.

그런데 이 코드도 문제가 있었다. 11번 테스트케이스에서 시간초과가 났다. 정확도 96... 열불이 났지만 난 포기하지 않지...

 

new_sum이 작은순으로 정렬한다면 최솟값부터 visited에 들어갈 확률이 높아지니 쓸모없는 원소들이 q에 들어가는게 더 적어질 거라 판단했고, new_sum을 맨 앞으로 옮기고 deque가 아닌 최소힙을 사용하기 위해 heapq를 사용했다.

 

그리고 마침내 정답!!!

 

정답 코드

import heapq
def solution(board):
    answer = 1e9

    dx = [0,0,1,-1]
    dy = [-1,1,0,0]
    
    # 위,아래 = 0 / 왼,오 = 1
    # 이전 d를 저장해두고 d가 바뀌면 코너가 생긴 것이므로 +500 해주기
    d = [0,0,1,1]
    n = len(board)
    
    def bfs():
        nonlocal answer
        visited = [[1e9 for _ in range(n)] for _ in range(n)]
        visited[0][0] = 0
        q = []
        # 비용, x, y, 현재방향
        heapq.heappush(q,(0,0,0,-1))
        
        while q:
            c_sum,x,y,cd = heapq.heappop(q)


            if x == n-1 and y==n-1:
                answer = min(c_sum,answer)
                continue
            
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if nx<0 or ny<0 or nx>=n or ny>=n or board[nx][ny]==1:
                    continue
                    
                if cd == -1:
                    new_sum = c_sum + 100
                elif d[cd] != d[i]:
                    new_sum = c_sum + 600
                else:
                    new_sum = c_sum + 100

                if (cd!=-1 and nx==x-dx[cd] and ny == y-dy[cd]) or visited[nx][ny] < new_sum - 500:
                    continue
                
                visited[nx][ny] = min(visited[nx][ny],new_sum)
                heapq.heappush(q,(new_sum,nx,ny,i))
    
    bfs()
            
    return answer

 

11번 문제 통과 뿐만 아니라 전체적인 시간도 엄청 많이 개선됐다!!

 

 

+7점이나 주는 문제였다 디버깅 열심히 하면서 푼 보람이 있구나

포기하지 않길 참 잘했다 ^ __ ^