[코드트리] 마법의 숲 탐색

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/magical-forest-exploration/description

코딩테스트 기출 문제 설명: 마법의 숲 탐색 | 코드트리

---

솔루션

from collections import deque

R, C, K = map(int, input().split())


dxy = [(-1,0),(0,1),(1,0),(0,-1)]

A = [[0] * C for _ in range(R+3)]
def in_range(r, c):
    return 0<=r<R+3 and 0<=c<C

# 골렘의 중심이 (r,c)로 이동할 수 있는지 확인하는 함수
def can_go(r, c):
    check_pos = [
        (r-2, c), 
        (r-1, c-1), (r-1, c), (r-1, c+1), 
        (r, c-1), (r, c), (r, c+1), 
        (r+1, c)
    ]
    for nr, nc in check_pos:
        if not in_range(nr, nc) or A[nr][nc] != 0:
            return False
    return True

# num번 골렘이 c열, 출구방향 d로 내려보내는 함수
def drop(num, c, d):
    r = 1 # 골렘의 중심은 (1,c)에서 시작
    while True:
        # 1: 남쪽으로 이동
        if can_go(r+1, c):
            r, c = r+1, c
        # 2: 서쪽으로 회전하며 이동
        elif can_go(r+1, c-1):
            r, c = r+1, c-1
            d = (d-1+4)%4 
        # 3: 동쪽으로 회전하며 이동
        elif can_go(r+1, c+1):
            r, c = r+1, c+1
            d = (d+1)%4
        else:
            break
    # 골렘의 몸체 일부라도 숲을 벗어나면 리셋
    if r < 4: # r-1 < 3 이면 숲을 벗어난것
        return -1, -1
    # 최종 위치에 골렘 정보 기록
    A[r][c] = num
    for idx, (dx, dy) in enumerate(dxy):
        nr, nc = r+dx, c+dy
        # 출구는 음수, 나머지는 양수로 기록
        A[nr][nc] = -num if d == idx else num
    return r, c

def reset_map():
    for r in range(R+3):
        for c in range(C):
            A[r][c] = 0

# 정령이 (r, c)에서 탐색을 시작하여 도달할 수 있는 가장 남쪽 행을 찾는 함수
def tour(r, c):
    q = deque()
    visited = [[False] * (C) for _ in range(R+3)]
    visited[r][c] = True
    q.append((r,c))
    max_r = r # 가장 남쪽행 번호를 기록할 변수
    while q:
        curr_r, curr_c = q.popleft()
        for dx, dy in dxy:
            nr, nc = curr_r+dx, curr_c+dy
            if not in_range(nr, nc) or visited[nr][nc] or A[nr][nc] == 0:
                continue
            
            # 1. 같은 골렘의 몸체 내부이거나 
            # 2. 현재 위치가 출구이면 인접한 다른 골렘으로 이동 가능
            if abs(A[curr_r][curr_c]) == abs(A[nr][nc]) or A[curr_r][curr_c] < 0:
                visited[nr][nc] = True
                q.append((nr, nc))
                max_r = max(max_r, nr) # 가장 남쪽 행 갱신

    return max_r
            
total_score = 0

for num in range(1, K+1):
    c, d = map(int, input().split())
    c -= 1

    # 현재 정령의 골램 내려보냄
    r, c = drop(num,c, d)

    if r == -1: # 골렘이 숲을 벗어남
        reset_map()
    else:
        final_row = tour(r, c)
        total_score += final_row - 2
print(total_score)