[탐색] 경주로 건설 (파이썬)

문제 설명

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

프로그래머스

문제 풀이

• 방향에 따라 비용이 변하는 문제이다.
• 방향을 기억해줘야 하고 특정 위치에서 코너가 발생하더라도 방향에 따라 결과값이 바뀔 수 있다.
• 그러므로 위치에서의 비용을 기록하는 cost라는 그래프는 각각의 방향에 따라 비용을 저장해야함
• 큐에는 현재의 방향과 다음에 갈 방향이 직선인지 체크 할 dic이라는 변수도 저장(상하라면 0, 좌우라면1)
• 나머지는 평범한 bfs 문제

 

소스코드

from collections import deque

INF = int(1e9)
#상,하,좌,우
dx = [-1,1,0,0] #k가 0,1 이면 q에 방향 0 넣어주기
dy = [0,0,-1,1] #k가 2,3 이면 q에 방향 1 넣어주기

def solution(gr):
    answer = INF
    n = len(gr)
    cost = [[[INF]*4 for j in range(n)] for i in range(n)]
    cost[0][0]=[0,0,0,0]
    q=deque()
    			# 0,0에서의 첫 이동 지점인 (0,1)과 (1,0)을 큐에 먼저 넣어줌
    for xx,yy in [[0,1],[1,0]]:
        if gr[xx][yy]==1:
            continue
        if([xx,yy]==[1,0]):
            a,b,c=0,1,1
        else:
            a,b,c=1,3,3
        cost[xx][yy][b]=100
        q.append((xx,yy,a,c))
    while(q):
    				# x,y좌표, 직선인지 판별할 dic, 현재 위치 왔을때의 방향
        x,y,dic,before = q.popleft()
        if([x,y]==[n-1,n-1]):
            answer=min(answer,cost[x][y][before])
            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:
                continue
            if gr[nx][ny]==1:
                continue
            nextDic = 0 if i in [0,1] else 1 #[0,1]은 dx,dy에서의 (-1,0),(1,0)을 뜻함(상하). 좌우라면 1
            c = 600 if nextDic!=dic else 100
            if cost[nx][ny][i]<cost[x][y][before]+c:
                continue
            cost[nx][ny][i]=cost[x][y][before]+c
            q.append((nx,ny,nextDic,i))
    return answer
            

print(solution([[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]]))