[백준_3709]레이저빔은 어디로 with Python

백준(BOJ) 시뮬레이션 문제집: 레이저빔은 어디로(골드 5)

문제 출처: https://www.acmicpc.net/problem/3709

3709번: 레이저빔은 어디로

 

1. 알고리즘

처음에 굳이 DFS/BFS로 풀어야 하나 싶어서 while문으로 좌표를 이동하는 식으로 작성하고자 했지만,,,

시간초과, 시간초과, 실패, 실패....알고리즘 분류를 보니 DFS가 있길래 재귀로 작성하고 바로 통과했던 문제.

레이저 위치 표현을 위해 보드를 N*N이 아닌 (N+2)*(N+2)로 하고,

이동에 있어서는 재귀적으로 문제에서 하라는 대로만 하면 됐다.

추가로, '0 0'이 나오는 경우는 사실상 없다. 그 부분은 구현하지 않아도 통과함.

• 테스트케이스 횟수(T)만큼 반복
• (n+2)*(n+2)크기의 보드를 생성, 우향우 거울 위치에 '-1'값으로 표기해줌
• 레이저 입력 위치를 입력받고, 위치에 따라 레이저의 방향을 구함
  • find_direction함수 작성
  • 행이 0이면 남쪽↓ / 행이 n+1이면 북쪽↑ / 열이 0이면 동쪽→ / 열이 n+1이면 서쪽←
• 레이저 위치, 레이저 방향을 사용하여 레이저를 한 칸씩 이동
  • move_laser함수(재귀) 작성
  • 방향에 따라 한 칸 이동
  • 이동한 칸 값에서 행이 0 또는 n+1이거나 열이 0 또는 n+1이면 레이저 값을 반환
  • 보드의 이동칸이 0이 아니면(거울이면)
    • 90도 회전한 방향을 계산
    • 만약 보드의 칸 값이 새 방향과 같으면 이전에도 동일한 방향의 레이저가 왔다는 뜻▶무한반복
      • '0 0' 반환
    • 보드 이동칸을 새 방향 값으로 갱신
  • move_laser 함수 호출
• 반환된 좌표값 출력

 

2. 유의 사항

• 입력값으로 주어지는 좌표는 1부터 시작

 

3. 어려웠던 점, 해결방법

 

4. 소스코드

상세 코드 설명은 주석 참고

import sys
 
#레이저 방향 반환 함수
def find_direction(coordinate):
    _x, _y = coordinate
    
    if _x == 0:
        return 2
    elif _x == n+1:
        return 0
    elif _y == 0:
        return 1
    elif _y == n+1:
        return 3
 
#레이저 이동 재귀함수
def move_laser(start, direction):
    global out_x, out_y
    _x, _y = start
    _x, _y = _x + dx[direction], _y + dy[direction] #한 칸 이동
    
    #만약 이동좌표가 보드 밖이면 마지막 좌표 값 설정 후 반환
    if _x in (0, n+1) or _y in (0, n+1):
        out_x, out_y = str(_x), str(_y)
        return
    
    #거울을 만나는 경우
    if board[_x][_y] != 0:
        new_direction = (direction+1) % 4   #새 방향 계산
        
        #보드 값이 새 방향과 같은 경우(무한반복)
        if board[_x][_y] == new_direction:
            out_x, out_y = '0', '0'
            return
        
        #보드 값을 새 방향 값으로 갱신
        board[_x][_y] = new_direction
        direction = new_direction
    
    #다음 칸으로 이동
    move_laser((_x, _y), direction)
 
 
input_func = sys.stdin.readline
if __name__ == '__main__':
    T = int(*map(int, input_func().split()))
 
    for _ in range(T):
        n, r = map(int, input_func().split())
        
        #보드 생성, 거울 위치 표시
        board = [[0]*(n+2) for _ in range(n+2)]
        for _ in range(r):
            x, y = map(int, input_func().split())
            board[x][y] = -1
        
        #레이저 시작지점 설정, 방향 설정
        laser = tuple(map(int, input_func().split()))
        laser_direction = find_direction(laser)
        
        #이동 좌표 설정(북, 동, 남, 서)
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        out_x, out_y = -1, -1   #레이저 빔의 마지막 좌표 초기 설정
        #레이저 이동
        move_laser(laser, laser_direction)
        print(out_x+' '+out_y)

 

5. 고민

• while문으로 작성했던 코드는 뭐가 문제였을까..?