[코드트리 챌린지] 1주차 - 거울에 레이저 쏘기 2(Python)

문제링크

https://www.codetree.ai/cote/13/problems/shoot-a-laser-in-the-mirror-2?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

핵심

1.  방향에 따라 움직임 : dx-dy 테크닉 사용 

2. 격자 내 움직임  : in_range 함수로 판단

3. k에 따른 방향 판단 : n에 대한 주기성 활용

    → 예시) 1 ~ 12 - 0 ~ 11 : 0base로 변경 ≫ 「동(0)남(1)서(2)북(3)」 "0 ~ 2인 위쪽변"은 "몫이 0"이 되므로 + 1  ≫ 왼쪽변이 4가 되므로 % 4  ∴ ((k // n) + 1)%4

4. k에 따른 시작점의 좌표 판단 

    「3.k에 따른 방향 판단」 에서 방향을 판단하면 어디 변인지 파악 판단 ≫ cr, cc(시작 좌표) 판단 

    → 예시) k=0, 1, 2(0base)일 때 cur_dir = 1 위쪽변 ≫ cr = 0, cc = 0 % n

    → 예시) k=3, 4, 5(0base)일 때 cur_dir = 2 오른쪽변 ≫ cr = k % n , cc = n - 1

    → 예시) k=6, 7, 8(0base)일 때 cur_dir = 3 아랫쪽변, 인덱스와 번호가 반대로 붙여진 상태 ≫ cr  =  n - 1 , cc  = n - 1 - (k % n)

    → 예시) k=9, 10, 11(0base)일 때 cur_dir = 0 왼쪽변, 인덱스와 번호가 반대로 붙여진 상태 ≫ cr  =  n - 1 - (k % n) , cc  = 0

5. 거울일 때 방향 전환 

• \ 부딪힐 때 방향 전환
  • 남(1) ↔ 동(0) : (이진법) 남(01) ↔ 동(00)
  • 서(2) ↔ 북(3) : (이진법) 남(10) ↔ 동(11)
• / 부딪힐 때 방향 전환
  • 남(1) ↔ 서(2) : (이진법) 남(01) ↔ 서(10)
  • 북(3) ↔ 동(0) : (이진법) 북(11) ↔ 동(00)
• 판단 방법 1. if문 활용

# / 거울일 때 방향전환
def slash(cur_dir):
    if cur_dir == 1:
        cur_dir = 2
    elif cur_dir == 2:
        cur_dir = 1
    elif cur_dir == 3:
        cur_dir = 0
    else:
        cur_dir = 3
    return cur_dir

• 판단 방법2. XOR
  • \ :  남(01) ↔ 동(00), 남(10) ↔ 동(11)
    • 첫 번째 비트만 0 ↔ 1 변경 : ^01 = ^ 1
  • / : 남(01) ↔ 서(10), 북(11) ↔ 동(00)
    • 첫 번째, 두 번째 모두 변경 : ^11 = ^3

# 거울일 때 방향전환
def reflect(cur_dir, slash):
    if slash == '/':
        return cur_dir ^ 3
    return cur_dir ^ 1

 

코드(Python)

n = int(input())
board = [list(input()) for _ in range(n)]
k = int(input())
# False : \ 에 부딪힐 때 방향전환을 어떻게 해?
# cur_dir = 1 -> touch -> cur_dir = 3
# 남(1) <-> 동(0) 01 00
# 서(2) <-> 북(3) 10 11 ^= 01 == 1
# True / 에 부딪힐 때 방향전환을 어떻게 해?
# 남(1) <-> 서(2) 01 10
# 북(3) <-> 동(0) 11 00 ^= 11 == 3

# 좌표
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

k -= 1
cur_dir = ((k // n) + 1) % 4 # 방향
if cur_dir == 1:
    cr, cc = 0, k % n
elif cur_dir == 2:
    cr, cc = k % n, n - 1
elif cur_dir == 3:
    cr, cc = n - 1, (n - 1) - (k % n)
else:
    cr, cc = (n - 1) - (k % n), 0

# 격자 내 존재 체크
def in_range(r, c):
    return 0 <= r < n and 0 <= c < n
# / 거울일 때 방향전환
def reflect(cur_dir, slash):
    if slash == '/':
        return cur_dir ^ 3
    return cur_dir ^ 1

# 거울상태 체크 후 방향 전환 후 이동
def reflection_move(cur_dir, cr, cc):
    cur_dir = reflect(cur_dir, board[cr][cc])
    nr = cr + dr[cur_dir]
    nc = cc + dc[cur_dir]
    return cur_dir, nr, nc

# 초기방향, 초기좌표
def simulate(cur_dir, cr, cc):
    cnt = 0
    while in_range(cr, cc):
        cur_dir, cr, cc = reflection_move(cur_dir, cr, cc)
        cnt += 1
    return cnt

print(simulate(cur_dir, cr, cc))