[Python/프로그래머스]경주로 건설_[BFS]

 

 

 

 

 

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

프로그래머스

 

🐾 20221022

 

 

 

from collections import deque 
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def solution(board):
    n = len(board)
    def bfs(x,y,cost,dir) :
        vis = [[0]*n for _ in range(n)]
        vis[0][0] = 1
        q = deque([[x,y,cost,dir]])
        while q :
            x,y,cost,idx = q.popleft()
            for i in range(4) :
                nx,ny = x + dx[i], y + dy[i]
                # 벽이 아니고 내부라면 
                if 0<=nx<n and 0<=ny<n and board[nx][ny] != 1 :
                	# 방향이 같다면 
                    if i == idx : new_cost = cost + 100 
                    # 방향이 다르다면 
                    else : new_cost = cost + 600
                    
                    # 가본적이 없거나 가봤어도 지금 가는게 더 최소값일 때 
                    if (vis[nx][ny] == 0 or ((vis[nx][ny]!=0) and vis[nx][ny] > new_cost)):
                        q.append([nx,ny,new_cost,i])
                        vis[nx][ny] = new_cost 
        return vis[n-1][n-1]
                
    return min(bfs(0,0,0,0),bfs(0,0,0,1))

 

 

 

거의 다 맞혔는데

나는 한번에 deque에 [0,0,0,0]과 [0,0,0,1]을 같이 넣어서 틀렸다.ㅎㅎㅎ

위  코드처럼 각자 구한뒤에 최소값을 답으로 return 해야한다. 

 

 

 

그리고 cost = cost + 100 이런식으로 해서

해당 칸에서 덱에 숫자를 넣는다면

해당 칸에서 움직이는 다른 칸은 이미 한번 더해진 cost에 또 더한 값이 되어서 틀린다. 

 

 

 

방향이 같으면 new_cost = cost + 100, 

방향이 다르면 new_cost = cost + 600이 된다는 것을 잊지말기 

 

 

 

600인 이유는 500 + 100이다. (꺽어야하고, 직진선로도 설치해야해서)

 

 

 

이 코드의 핵심은! 

 

# 가본적이 없거나 가봤어도 지금 가는게 더 최소값일 때 
if (vis[nx][ny] == 0 or ((vis[nx][ny]!=0) and vis[nx][ny] > new_cost)):
	q.append([nx,ny,new_cost,i])
    vis[nx][ny] = new_cost

이라고 생각한다. 

 

가본적이 없거나 ! 가본적이 있다고 해도 지금 가는게 더 적은 비용일때 !

 

---

 

 

이후에 다시 풀어봤다. 

from collections import deque 
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def solution(board):
    answer = int(1e9)
    n = len(board)
    q = deque([[0,0,0,1],[0,0,0,0]])
    mp = [[int(1e9)]*n for _ in range(n)] 
    
    while q :
        x,y,val,dir = q.popleft()
        
        if x == (n-1) and y == (n-1) : answer = min(answer,val)
        for i in range(4) :
            nx,ny = x + dx[i], y + dy[i]
            if 0<=nx<n and 0<=ny<n and board[nx][ny]==0 :
                if dir==i : 
                    if mp[nx][ny] < val+100 : continue 
                    mp[nx][ny] = val+100
                    q.append([nx,ny,val+100,dir])
                else : 
                    if mp[nx][ny] < val+600 : continue 
                    mp[nx][ny] = val+600
                    q.append([nx,ny,val+600,i])
    return answer

원래랑 조금 다르긴 한데 25번 테케에서만 틀린다.

 

 

 

왜지?!!!??!