-
[탐색] 경주로 건설 (파이썬)코딩 테스트/프로그래머스 2023. 4. 22. 19:59
문제 설명
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]]))
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[탐색] 자물쇠와 열쇠 (파이썬) (0) 2023.04.25 [이분탐색] 입국심사 (파이썬) (0) 2023.04.22 [힙] 디스크 컨트롤러 (파이썬) (0) 2023.04.21 [이분 탐색] 징검다리 건너기 (파이썬) (0) 2023.04.20 [투 포인터] 보석 쇼핑 (파이썬) (0) 2023.04.20