[백준] [BFS] 2344. 거울

2344. 거울

2344번: 거울

 

 최적화할 수 있는 더 좋은 방법 (남곤풀이)

• 출발지 → 도착지 = 도착지→ 출발지 같으니까 
  • 하나 구할때 미리 넣어주고
  • 구하려는 위치값이 0이 아닐 때만 새로 계산하는 걸로 해주면 
  • 시간을 반으로 최적화 가능

 

• 내 풀이
  • graph 바깥으로 한칸씩을 더 만들고
  • 왼쪽, 아래, 오른쪽, 위 순으로 for문을 돌면서 나오는 칸의 번호를 넣어준다
  • 동북 / 서남 으로 거울만나면 방향 바꿔주면서 이동
  • 범위밖으로 나오면 해당 위치 리턴해서 해당위치에 맞는 번호값 출력

from collections import deque

def bfs(i,j,d):
    queue=deque()
    queue.append((i,j,d))

    nx,ny=0,0
    while queue:
        x,y,d=queue.popleft()
        if graph[x][y]==1:
            if d==0 or d==2:
                d+=1
            else:
                d-=1
            
        nx=x+dx[d]
        ny=y+dy[d]

		#정해진 범위밖으로 나오면 해당 위치 출력
        if nx<=0 or nx>n or ny<=0 or ny>m: 
            return (nx,ny)
        queue.append((nx,ny,d))

    

n,m=map(int,input().split())
#가장 바깥 칸 만들기
graph=[[0 for _ in range(m+2)]]+[[0]+list(map(int,input().split()))+[0] for _ in range(n)]+[[0 for _ in range(m+2)]]
#동북서남
dx=[0,-1,0,1]
dy=[1,0,-1,0]

#나오는칸 번호 매겨주기
idx=0
for i in range(1,n+1):
    idx+=1
    graph[i][0]=idx
for i in range(1,m+1):
    idx+=1
    graph[n+1][i]=idx
for i in range(n,0,-1):
    idx+=1
    graph[i][m+1]=idx
for i in range(m,0,-1):
    idx+=1
    graph[0][i]=idx


result=[]
#출력되는 위치에 맞는 값이 번호값
for i in range(1,n+1):
    endX, endY=bfs(i,1,0)
    result.append(graph[endX][endY])
for i in range(1,m+1):
    endX, endY=bfs(n,i,1)
    result.append(graph[endX][endY])
for i in range(n,0,-1):
    endX, endY=bfs(i,m,2)
    result.append(graph[endX][endY])
for i in range(m,0,-1):
    endX, endY=bfs(1,i,3)
    result.append(graph[endX][endY])

print(*result)