[삼성 SW 역량테스트 2024 상반기 오후 1번 문제] 마법의 숲 탐색

https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration?page=1&pageSize=5

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

 

 

 

정령의 현재 위치에서 (1)아래, (2)아래왼쪽, (3)아래오른쪽 으로 이동하게 된다. 

 

canGo 함수를 확인해보자.

골렘의 이동을 기준으로 보면 위 그림과 같이 x표시한부분을 거치게 되므로 x표시된부분이 비어있어야한다.

 

 

down함수를 통해 (1)을 이동하지 못하면 (2)를 확인해보고 (2)가 안되면 (3)을 하면 된다. 

재귀적으로 들어가다 (1),(2),(3)을 모두 True하지 못하면 움직이지 못하므로 그 밑으로 이동하면 된다.

(1)을 가다가 (1)을 통과하지 못하고 (2)를 들어간 이후 다시 (2)로 가면서 계속 아래왼쪽으로 돌아갈 수 있다.

 

import sys 
sys.stdin=open('input.txt', 'r')
from collections import deque

MAX_L = 10 #70  # R과 C의 최대는 70이라고 명시되어 있음 
R,C,K = 0,0,0
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
A = [[0]*MAX_L for _ in range(MAX_L+3)]     # 가장 넓은 숲을 가정하고 골렘이 튀어 나온것을 고려하여 3만큼 크기를 더 갖음 
isExit = [[False]*MAX_L for _ in range(MAX_L+3)]
answer = 0

def showboard(A):
    for i in range(len(A)):
        print(A[i])

# 숲의 범위안에 있는지 확인 
def in_range(y,x):
    return 0<=x<C and 3<=y<R+3

# 숲 골렘 초기화 -> 숲에 있는 골렘들이 모두 빠져 나감 
def resetMap():
    for i in range(R+3):        # 숲의 범위 만큼만 
        for j in range(C):
            A[i][j]=0
            isExit[i][j]=False
            
# 골렘의 중심 (x,y)가 위치할 수 있는지 확인 
# 골렘의 생김새와 북쪽에서 남쪽으로 내려오는것을 고려할 때 (x,y)와 (x,y-1)의 범위를 모두 확인해야한다.
def canGo(y, x):
    flag = (0 <= x-1 and x+1 < C) and (y+1 < R + 3)     # 먼저 내려갈 수 있는지 부터 확인 
    flag = flag and (A[y - 1][x - 1] == 0)
    flag = flag and (A[y - 1][x] == 0)
    flag = flag and (A[y - 1][x + 1] == 0)
    flag = flag and (A[y][x - 1] == 0)
    flag = flag and (A[y][x] == 0)
    flag = flag and (A[y][x + 1] == 0)
    flag = flag and (A[y + 1][x] == 0)
    return flag

# 정령이 움직일 수 있는 모든 범위를 확인하고 도달할 수 있는 최하단 행을 반환 
def BFS(y,x):
    result = y  # 현재 y위치
    visit = [[False]*C for _ in range(R+3)]
    visit[y][x] = True 
    Q = deque([(y,x)])
    while Q:
        cur_y,cur_x = Q.popleft()
        for k in range(4):
            ny,nx = cur_y+dy[k],cur_x+dx[k]
            if in_range(ny,nx) and not visit[ny][nx]:   # 숲 범위안에 있고, 첫 방문 
                # (같은 골램안에서(골램 id번호가 같음) 움직이거나) or (0이 아닌 서로 다른 번호의 골램 and 현재위치가 딱 탈출구라면)
                if (A[ny][nx] == A[cur_y][cur_x]) or (A[ny][nx]!=0 and isExit[cur_y][cur_x]):
                    Q.append((ny,nx))               # 새로운 위치로 이동 가능 
                    visit[ny][nx]=True 
                    result = max(result, ny)        # 더 아래로 가는것을 추구하기 때문에 
    return result



def down(y,x,d,id):
    if canGo(y+1,x):                # 현재 위치에서 한칸 아래(y+1)로 갈 수 있는지 확인 
        down(y+1,x,d,id)            # 그대로 한칸 밑으로 
    elif canGo(y+1,x-1):            # 왼쪽 아래로 갈수 있는 경우  
        down(y+1,x-1,(d+3)%4,id)    # 방향이 바뀜 
    elif canGo(y+1,x+1):            # 오른쪽 아래로 갈수 있는 경우 
        down(y+1,x+1,(d+1)%4,id)    # 방향을 바꿔 오른쪽 아래로 이동 
    else:
        # 1,2,3번 경우 모두 이동 할 수 없는 경우 
        if not in_range(y-1,x-1) or not in_range(y+1,x+1):      # 골렘의 일부가 숲을 벗어나는 경우 모든 골렘은 숲을 빠져나감 
            resetMap()
        else:
            # 골렘이 숲 안에 정착 
            A[y][x]=id
            for k in range(4):
                A[y+dy[k]][x+dx[k]] = id                    # 골렘이 차지하는 범위 상하좌우
            isExit[y+dy[d]][x+dx[d]] = True                 # 골렘의 출구 표시 
            global answer 
            answer += BFS(y,x)-3+1

def main():
    global R,C,K
    R,C,K=map(int, input().split())      # RxC: 숲의크기, K: 정령의 수 
    # board = [[0]*C for _ in range(R)]     # 숲 크기의 board를 따로 만들지 않음 
    for id in range(1,K+1):
        x, d, = map(int,input().split())     # x: 골렘이 출발하는 열, d: 골렘의 출구 방향 정보 
        down(0, x-1, d, id)                  # y=0에서 시작   

    print(answer)
    
if __name__=="__main__":
    main()