[삼성 SW 역량테스트 기출] 마법의 숲 탐색

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

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

# 숲의 동쪽, 서쪽, 남쪽은 마법의 벽으로 막혀 있으며, 정령들은 숲의 북쪽을 통해서만 숲에 들어올 수 있습니다.

# 총 K명의 정령은 각자 골렘을 타고 숲을 탐색
# 각 골렘은 십자 모양의 구조를 가지고 있으며, 중앙 칸을 포함해 총 5칸을 차지
# 골렘의 중앙을 제외한 4칸 중 한 칸은 골렘의 출구
# 정령은 어떤 방향에서든 골렘에 탑승할 수 있지만, 골렘에서 내릴 때에는 정해진 출구를 통해서만 내릴 수 있습니다.

# i번째로 숲을 탐색하는 골렘은 숲의 가장 북쪽에서 시작해 골렘의 중앙이 ci 열이 되도록 하는 위치에서 내려오기 시작합니다. 
# 초기 골렘의 출구는 di 의 방향에 위치해 있습니다.

# < 더 이상 움직이지 못할 때까지 해당 과정을 반복 >
# 1. 남쪽으로 한 칸 내려갑니다.(초록색 칸들이 비어있을 때에만 남쪽으로 내려갈 수 있습니다.)
# 2. (1)의 방법으로 이동할 수 없으면 서쪽 방향으로 회전하면서 내려갑니다.
# 초록색 칸들이 비어있을 때에만 서쪽 방향으로 회전하면서 내려갈 수 있습니다.
# 서쪽 방향으로 한 칸 이동을 한 뒤 내려가기 때문에 골렘을 기준으로 서쪽 한 칸이 모두 비어 있어야 함에 유의
# 3. (1)과 (2)의 방법으로 이동할 수 없으면 동쪽 방향으로 회전하면서 내려갑니다.
# 4. 골렘이 이동할 수 있는 가장 남쪽에 도달해 더이상 이동할 수 없으면 정령은 골렘 내에서 상하좌우 인접한 칸으로 이동이 가능합니다. 
# 단, 만약 현재 위치하고 있는 골렘의 출구가 다른 골렘과 인접하고 있다면 해당 출구를 통해 다른 골렘으로 이동할 수 있습니다.
# 정령은 갈 수 있는 모든 칸 중 가장 남쪽의 칸으로 이동하고 이동을 완전히 종료

# 정령의 최종 위치의 행 번호의 합을 구해야 하기에 각 정령이 도달하게 되는 최종 위치를 누적해야 합니다.

# 만약 골렘이 최대한 남쪽으로 이동했지만 골렘의 몸 일부가 여전히 숲을 벗어난 상태라면, 
# 해당 골렘을 포함해 숲에 위치한 모든 골렘들은 숲을 빠져나간 뒤 다음 골렘부터 새롭게 숲의 탐색을 시작합니다. 
# 단, 이 경우에는 정령이 도달하는 최종 위치를 답에 포함시키지 않습니다.

# 출력 : 골렘들이 숲에 진입함에 따라 각 정령들이 최종적으로 위치한 행의 총합

import sys
from collections import deque

input = sys.stdin.readline

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

area = [[0]*C for _ in range(R+3)]
isExit = [[False]*C for _ in range(R+3)]

answer = 0

dx = [-1,0,1,0]
dy = [0,1,0,-1]

def inRange(x,y):
    return 3 <= x < R+3 and 0 <= y < C

def debug():
    for a in area:
        print(a)
    print()

def debug_exit():
    for a in isExit:
        print(a)
    print()

def canGoDown(x,y):
    if 0 <= x+2 < R+3 and 0 <= y-1 < C and 0 <= y+1 < C:
        if area[x+2][y] == 0 and area[x+1][y-1] == 0 and area[x+1][y+1] == 0:
            return True
    return False

def canGoLeft(x,y):
    if 0 <= x+2 < R+3 and 0 <= y-2 < C:
        if area[x-1][y-1] == 0 and area[x][y-2] == 0 and area[x+1][y-1] == 0 and area[x+1][y-2] == 0 and area[x+2][y-1] == 0:
            return True
    return False

def canGoRight(x,y):
    if 0 <= x+2 < R+3 and 0 <= y+2 < C:
        if area[x-1][y+1] == 0 and area[x][y+2] == 0 and area[x+1][y+1] == 0 and area[x+1][y+2] == 0 and area[x+2][y+1] == 0:
            return True
    return False

def move(x,y,d,index):

    if canGoDown(x,y):
        return move(x+1,y,d,index)
    elif canGoLeft(x,y):
        return move(x+1,y-1,(d+3)%4,index)
    elif canGoRight(x,y):
        return move(x+1,y+1,(d+1)%4,index)
    else:
        area[x][y] = index
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            area[nx][ny] = index
        isExit[x + dx[d]][y + dy[d]] = True
        return x, y

def bfs(x,y):

    q = deque([(x,y)])
    visited = [[False]*C for _ in range(R+3)]
    visited[x][y] = True

    maximum_row = -1

    while q:
        cx, cy = q.popleft()
        maximum_row = max(maximum_row, cx)
        
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]

            if 0 <= nx < R+3 and 0 <= ny < C and not visited[nx][ny]:
                if area[cx][cy] != 0 and area[cx][cy] == area[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx,ny))
                else:
                    if area[cx][cy] != 0 and area[nx][ny] != 0 and isExit[cx][cy]:
                        visited[nx][ny] = True
                        q.append((nx,ny))
    return maximum_row-2

for index in range(1,K+1):
    c, d = map(int,input().split())
    tx, ty = move(1,c-1,d,index)

    if not inRange(tx-1,ty) or not inRange(tx,ty) or not inRange(tx,ty-1) or not inRange(tx,ty+1) or not inRange(tx+1,ty):
        area = [[0]*C for _ in range(R+3)]
        isExit = [[False]*C for _ in range(R+3)]
        continue

    answer += bfs(tx,ty)

print(answer)

 

이번 문제는 2024년 삼성 코테 기출 문제로 십자모양으로 이루어진 영역 K개를 테트리스처럼 1) 아래방향으로 이동 2) 이동이 불가하다면 왼쪽 방향으로 회전 후 아래로 이동 3) 이것도 불가하다면 오른쪽 방향으로 회전 후 아래로 이동시킨 후 상하좌우로 이동할 수 있는 최대 행을 누적시키는 문제이다.

 

이전에 풀었을 때는 성공하지 못하여 다시 풀어보려고 했는데, 역시나 쉽지 않았다.

 

먼저 해당 문제에서 필요다고 생각한 함수는 다음과 같다.

• 해당 좌표를 기준으로 아래로 이동이 가능한지 여부를 확인하는 함수(canGoDown)
• 해당 좌표를 기준으로 왼쪽으로 이동이 가능한지 여부를 확인하는 함수(canGoLeft)
• 해당 좌표를 기준으로 오른쪽으로 이동이 가능한지 여부를 확인하는 함수(canGoRight)
• 해당 좌표를 기준으로 영역을 아래 / 왼쪽 / 오른쪽으로 이동시키는 함수(move)
• 연결된 영역들을 탐색하며 이동할 수 있는 최대 행을 구하는 함수(bfs)

문제의 해설을 참고하면서 잘못 접근한 부분과 보완할 점은 다음과 같다.

 

배운 점 및 느낀 점

1. 2차원 배열에 너무 많은 값(행, 열, 골렘 인덱스, 출구 여부..)을 담으면 헷갈릴 수 있기 때문에 최대한 필요한 값들을 분리하자. 행과 열은 필요없고 인덱스로만 영역을 구분시키고 출구 여부는 또 다른 배열을 선언해서 구분지으면 됨.
2. 좌표 이동에 대한 중간 과정이 필수가 아니라면 이동 과정을 전부 거치려고 하지 말고, 최종 도착 지점을 재귀로 찾아내서 이동만 시켜주자. 결국 모든 이동을 거치고 도착한 좌표만 구하면 되는데 중간중간에 값을 넣고 지우고를 반복하려다 보니 구현도 복잡하고 실수가 잦아진다.