BOJ 백준 파이썬 6087 레이저 통신

이전에 풀었던 문제인데,

그 때 당시, 해결하지 못하여 풀이를 봤었다.

이번에도 헤매다가 해결했다.

한 번 헤맨 문제는 확실하게 해결하지 못하면 다음에 와서도 헤매는게 맞는 것 같다.

예전에 봤던 풀이를 보니 굉장히 심플하고 센스있는 풀이였다.

하지만, 내 것이 아니었고 또 다른 비슷한 문제에도 그런 해결책을 떠올릴 수 있을까?

답은 아니었다.

조금 투박해보이지만 여러 문제에 공통적으로 적용되는, 내가 시험장에서 떠올릴 수 있는

풀이대로 풀었다.

3차원 배열+alpha가 들어간 문제로 alpha가 낯설고 헷갈리는 문제다.

 

일단 거울의 갯수가 1개 늘어나는 8가지 상황을 정리해보았다.

위 그림의 8가지 상황을 2가지 조건으로 압축할수 있다.

행 1칸 이동 후 열 1칸 이동, 열 1칸 이동 후 행 1칸 이동

pk=x,y가 어느에서 방향에서 왔는지 알려주는 값 x,y=현재 좌표, nx,ny=다음 좌표

코드로 나타내면 아래와 같다.

##열 이동 후 행 이동

 if (pk==0 or pk==1) and (k==2 or k==3):

                        if dist[k][nx][ny]>dist[pk][x][y]+1:

                             dist[k][nx][ny]=dist[pk][x][y]+1

                             q.append((k,nx,ny))

##행 이동 후 열 이동

elif (pk==2 or pk==3) and (k==0 or k==1):

                        if dist[k][nx][ny]>dist[pk][x][y]+1:

                             dist[k][nx][ny]=dist[pk][x][y]+1

                             q.append((k,nx,ny))

그리고 dist[k][x][y]의 정의를 명확하게 해야한다.

dist[k][x][y]=k방향(ex: k=0 →, k=1  ←, k=2  ↑, k=3  ↓)에서 왔을 때 x,y좌표에서의 거울의 최솟값이다.

주의해야할 점은 k의 값이 같더라도(같은 방향에서 왔더라도) 이전 좌표가 어디냐에 따라

값이 바뀔 수도 있다는 것이다.

그리고 큐에는 x,y 좌표 뿐만 아니라 k까지 넣어줬다.

어느 방향에서 왔는지 알려줄 뿐만 아니라 dist 값을 넣을 때 필요하기 때문이다.

같은 정점을 방문해야하는 이유는

아래 그림을 참고하면 될 것 같다.

k값이 같더라도 현재 좌표의 이전 좌표에 따라 값이 바뀌는 것을 확인할 수 있다.

삼차원 배열을 다루는 것이 익숙하지 않아서 그렇지

계속 곱씹고 마주하다보면 쉽게 되지 않을까 싶다.

 

import sys
from collections import deque
from itertools import combinations
 
 ##큐에 출발점 넣기
def start():
      global sx,sy,ex,ey
      ok=0
      for i in range(h):
        for j in range(w):
            if board[i][j]=='C':
                if ok==0: ## 첫 번째 발견 시작점
                  sx=i
                  sy=j
                  ok=1
                elif ok==1: #두 번째 발견 도착점
                    ex=i 
                    ey=j
                    return
                     
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
 
    w,h=map(int,input().split()) ##w=열,h=행
 
    board=[list(map(str,input())) for _ in range(h)]
    dist=[[[float('inf')]*w for _ in range(h)] for _ in range(4)] ## 4방향에서 오니까
    
    q=deque()
    ##큐에 출발점과 도착점 찾아주기 그리고 출발점은 큐에 넣기
    sx=0
    sy=0
    ex=0
    ey=0
    start()
    q.append((-9,sx,sy)) ##((px,py,x,y))
 
    for k in range(4):
        dist[k][sx][sy]=0
 
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
    while q:
      pk,x,y=q.popleft()
      for k in range(4):
           nx=x+dx[k]
           ny=y+dy[k]
           
           if 0<=nx<h and 0<=ny<w:
                if board[nx][ny]=='*':
                   continue
                if pk==-9: #출발점일 경우
                    dist[k][nx][ny]=0
                    q.append((k,nx,ny))
                    continue
 
                if (pk==0 or pk==1) and (k==2 or k==3):
                        if dist[k][nx][ny]>dist[pk][x][y]+1:
                             dist[k][nx][ny]=dist[pk][x][y]+1
                             q.append((k,nx,ny))
 
                elif (pk==2 or pk==3) and (k==0 or k==1):
                        if dist[k][nx][ny]>dist[pk][x][y]+1:
                             dist[k][nx][ny]=dist[pk][x][y]+1
                             q.append((k,nx,ny))
                             
                else:
                    if dist[k][nx][ny]>dist[pk][x][y]:
                           dist[k][nx][ny]=dist[pk][x][y]
                           q.append((k,nx,ny))
    res=float('inf')
    for k in range(4):
        if dist[k][ex][ey]!=float('inf') and dist[k][ex][ey]<res:
            res=dist[k][ex][ey]
    print(res)