[파이썬] 백준 6087 : 레이저 통신 (골드3)

[파이썬] 백준 6087 : 레이저 통신 (골드3)

6087번: 레이저 통신

 

---

문제

---

풀이

 

0. 방향성 생각

• 한 좌표마다 4방향을 받아서 현재 지점까지 사용한 거울 개수 (방향 바꾼 횟수) 저장
• 같은 좌표라도 들어오는 방향에 따라서 다른 노드라고 생각해야함
• 같은 노드라고 봐도 되는데 따로 처리를 해줘야해서 4방향 정의하는게 편함

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

w,h = map(int,input().split())
INF = w*h
arr = [list(input()) for _ in range(h)]
visit = [[[INF]*4 for _ in range(w)] for _ in range(h)]

location = [(j,i) for i in range(h) for j in range(w) if arr[i][j] == 'C']
sx,sy = location[0]
ex,ey = location[1]

• C 중 아무거나 시작점 끝점으로 설정
• visit 4방향 정의

2. 함수 정의

step = [(1,0),(0,1),(-1,0),(0,-1)]
q = deque([(sx,sy,dire,0) for dire in range(4)])

while q:
    
    x,y,d,m = q.popleft()
        
    for dire in range(4):
        dx,dy = step[dire]
        nx = x + dx
        ny = y + dy
        
        if 0<=nx<w and 0<=ny<h and arr[ny][nx] != '*':
            
            if d%2 == dire%2 and m < visit[ny][nx][dire]:
                q.append((nx,ny,dire,m))
                visit[ny][nx][dire] = m
            elif d%2 != dire%2 and m+1 < visit[ny][nx][dire]:
                visit[ny][nx][dire] = m+1
                q.append((nx,ny,dire,m+1))

• 시작점에서 x,y좌표에 현재 방향d, 사용한 거울 수 m을 추가적으로 넣는다.
• 벽이 아닌경우 진행방향과 이전 진행방향이 같은 경우, 다른경우 다르게 푼다.
• 같은 경우 거울 사용하지 않고, 최소값 갱신하는 경우에만 큐에 추가.
• 다른 경우 거울을 사용하고, 최소값 갱신하는 경우에만 큐에 추가.

3. 출력

if visit[ey][ex] == INF: print(-1)
else: print(min(visit[ey][ex]))

 

---

전체코드

BFS 풀이

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

w,h = map(int,input().split())
INF = w*h
arr = [list(input()) for _ in range(h)]
visit = [[[INF]*4 for _ in range(w)] for _ in range(h)]

location = [(j,i) for i in range(h) for j in range(w) if arr[i][j] == 'C']
sx,sy = location[0]
ex,ey = location[1]


step = [(1,0),(0,1),(-1,0),(0,-1)]
q = deque([(sx,sy,dire,0) for dire in range(4)])

while q:
    
    x,y,d,m = q.popleft()
        
    for dire in range(4):
        dx,dy = step[dire]
        nx = x + dx
        ny = y + dy
        
        if 0<=nx<w and 0<=ny<h and arr[ny][nx] != '*':
            
            if d%2 == dire%2 and m < visit[ny][nx][dire]:
                q.append((nx,ny,dire,m))
                visit[ny][nx][dire] = m
            elif d%2 != dire%2 and m+1 < visit[ny][nx][dire]:
                visit[ny][nx][dire] = m+1
                q.append((nx,ny,dire,m+1))

if visit[ey][ex] == INF: print(-1)
else: print(min(visit[ey][ex]))

 

다익스트라 풀이

import heapq as hq
import sys
input = lambda : sys.stdin.readline()

inf = 1e9
w,h = map(int,input().split())
arr = [list(input()) for _ in range(h)]
visit = [[[inf]*4 for _ in range(w)] for _ in range(h)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]

locs = [(j,i) for i in range(h) for j in range(w) if arr[i][j] == 'C']
sx,sy = locs[0]
ex,ey = locs[1]

def di():
    
    heap = [(0,i,sx,sy) for i in range(4)]

    while heap:
        m,d,x,y = hq.heappop(heap)

        if (x,y) == (ex,ey):
            return m

        for nd in range(4):

            dx,dy = dire[nd]
            nx = x + dx
            ny = y + dy

            if 0<=nx<w and 0<=ny<h and arr[ny][nx] != '*':
                if d%2 == nd%2 and m < visit[ny][nx][nd]:
                    hq.heappush(heap,(m,nd,nx,ny))
                    visit[ny][nx][nd] = m

                if d%2 != nd%2 and m+1 < visit[ny][nx][nd]:
                    hq.heappush(heap,(m+1,nd,nx,ny))
                    visit[ny][nx][nd] = m+1
print(di())

BFS라 500 / 다익이 100ms정도 나왔음.

발상은 node로 들어오는 방향마다 다를 수 있으므로 다른 node로 생각하는게 포인트. 그렇게 안짜고도 풀 수야 있는데 이게 편한듯

코드도 거의 비슷

 

코멘트

프로그래머스 경주로건설이랑 똑같은 문제

다익스트라로 풀어도 무방. 맵 크기가 작아서 그냥 BFS로 짰음