728x90

문제

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

정령들이 R행 C열의 격자 형태로 이루어진 마법의 숲을 탐색하려고 합니다. 격자는 가장 위를 1행, 가장 아래를 R행으로 합니다.

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

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

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

골렘은 숲을 탐색하기 위해 다음과 같은 우선순위로 이동합니다. 더 이상 움직이지 못할 때까지 해당 과정을 반복합니다.

(1) 남쪽으로 한 칸 내려갑니다.

위 그림의 초록색 칸들이 비어있을 때에만 남쪽으로 내려갈 수 있습니다.

(2) (1)의 방법으로 이동할 수 없으면 서쪽 방향으로 회전하면서 내려갑니다.

위 그림의 초록색 칸들이 비어있을 때에만 서쪽 방향으로 회전하면서 내려갈 수 있습니다. 이 때 서쪽 방향으로 한 칸 이동을 한 뒤 내려가기 때문에 골렘을 기준으로 서쪽 한 칸이 모두 비어 있어야 함에 유의합니다. 또한 이렇게 이동할 때 출구가 반시계방향으로 이동합니다.

(3) (1)과 (2)의 방법으로 이동할 수 없으면 동쪽 방향으로 회전하면서 내려갑니다.

위 그림의 초록색 칸들이 비어있을 때에만 동쪽 방향으로 회전하면서 내려갈 수 있습니다. 이 때 동쪽 방향으로 한 칸 이동을 한 뒤 내려가기 때문에 골렘을 기준으로 동쪽 한 칸이 모두 비어 있어야 함에 유의합니다. 또한 이렇게 이동할 때 출구가 시계방향으로 이동합니다.

골렘이 이동할 수 있는 가장 남쪽에 도달해 더이상 이동할 수 없으면 정령은 골렘 내에서 상하좌우 인접한 칸으로 이동이 가능합니다. 단, 만약 현재 위치하고 있는 골렘의 출구가 다른 골렘과 인접하고 있다면 해당 출구를 통해 다른 골렘으로 이동할 수 있습니다.

정령은 갈 수 있는 모든 칸 중 가장 남쪽의 칸으로 이동하고 이동을 완전히 종료합니다. 이때 정령의 위치가 해당 정령의 최종 위치가 됩니다. 아래 그림에서는 정령이 출구를 타고 6번째 행까지 이동이 가능합니다.

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

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

즉, 아래와 같이 숲이 텅 빈 상태에서 다음 골렘이 탐색을 시작합니다.

골렘들이 숲에 진입함에 따라 각 정령들이 최종적으로 위치한 행의 총합을 구하는 프로그램을 작성하세요. 숲이 다시 텅 비게 돼도 행의 총합은 누적되는 것에 유의합니다.

입력형식

첫 번째 줄에는 숲의 크기를 의미하는 R, C, 정령의 수 K가 공백을 사이에 두고 주어집니다.

그다음 줄부터 K개의 줄에 거쳐 각 골렘이 출발하는 열 ci, 골렘의 출구 방향 정보 di가 공백을 사이에 두고 주어집니다.

골렘의 출구 방향 정보 di는 0과 3 사이의 수로 주어지며 각각의 숫자 0,1,2,3은 북, 동, 남, 서쪽을 의미합니다.

5≤RC≤70
1≤K≤1000
2≤ci≤C−1
0≤di≤3

출력 형식

첫번째 줄에 각 정령들이 최종적으로 위치한 행의 총합을 출력하세요.

풀이

아이디어

핵심적인 아이디어는 “골렘이 입장하기 전의 위치를 어떻게 처리할 것”이냐 이다.

평소에 하듯이 격자를 rxc로 만들어 다루면 격자 내부를 판단하는데 엄청 머리가 아프다..

격자 내부를 판단하는 조건을 깔끔하게 할 수 있다면 그대로 진행..

하지만 새로운 힌트를 얻었다.

→ 격자를 늘리는 것!!

💙TIP

골렘이 입장하기 전의 상태를 표현하기 위해 격자를 위로 3칸 늘린다.

격자 밖으로 나가지 못하는 특징을 살리기 위해 격자를 바깥으로 둘러 쌓아준다.

전체 순서는 다음과 같다.

골렘의 이동
정령의 이동

골렘의 이동

골렘은 우선순위 방향에 따라 움직인다.

남 → 서 → 동 을 우선순위로 확인하고 더이상 움직이 못할 때까지 이동을 반복해야한다.

처음에 이동 반복 조건을 안보고 조금 시간을 낭비 해버림

남쪽 방향 선택
서쪽 방향 선택
동쪽 방향 선택

1,2,3 조건을 확인하며 더이상 움직이지 못할 때까지 반복하면 골렘의 이동이 끝난다.

def move_golem(in_y, di):
    x, y = 1, in_y  # 골렘이 입장 전 상태
    global board
    # 더이상 움직일 수 없을 때 까지
    while True:
        # 남쪽 이동
        # 왼아, 가아, 오아 빈칸
        if sum([board[x+1][y-1], board[x+2][y], board[x+1][y+1]]) == 0:
            x += 1  # 남쪽 이동

        # 서쪽 이동 -> 남쪽 이동
        # 왼위, 왼가, 왼아, 왼왼아, 왼아아 빈칸
        elif sum([board[x-1][y-1], board[x][y-2], board[x+1][y-1], board[x+1][y-2], board[x+2][y-1]]) == 0:
            y -= 1  # 서쪽 이동
            x += 1  # 남쪽 이동
            di = (di - 1) % 4   # 출구 반시계 이동

        # 동쪽 이동 -> 남쪽 이동
        # 오위, 오가, 오아, 오오아, 오아아 빈칸
        elif sum([board[x-1][y+1], board[x][y+2], board[x+1][y+1], board[x+1][y+2], board[x+2][y+1]]) == 0:
            y += 1  # 동쪽 이동
            x += 1  # 남쪽 이동
            di = (di + 1) % 4   # 출구 시계 이동

        # 더이상 이동 불가능
        else:
            break

    return x, y, di

골렘 셋팅

골렘이 한칸이라도 격자 밖이라면 격자 내부를 리셋하고 그때의 정령은 누적하지 않는 조건이 있다. 이를 위해 조건을 추가한다.

격자를 3칸을 늘렸기 때문에 이를 잘 생각해야한다.

골렘의 가운데가 최소 어디까지 와야 완벽히 격자 내부에 있을지 고민해보면 금방 답이 나온다.

골렘 가운데 X좌표가 4가 되면 모든 골렘이 격자 내부에 있을 수 있다.

is_board

골렘이 격자 밖으로 나간 경우, board를 reset하고, 골렘도 다 치우고, 저장한 출구도 reset한다.

set_golem

그렇지 않으면 이제 격자에 골렘을 위치시킨다.

골렘을 따로 구분하기 위해 전역변수 cnt를 이용해서 골렘에게 숫자를 부여했다.

board에 골렘을 위치시키고, 출구를 따로 저장해둔다.

처음에 각 골렘마다 출구를 저장하려고 생각했는데 굳이 그럴 필요가 없었다.

출구가 겹치는 일도 없다.

# 골렘이 튀어나갔는지 확인
def is_board(x):
    # x를 늘린 것을 고려해야함 / 골렘의 가운데가 4에 와야 골렘이 모두 안에 위치
    return x < 4

# 골렘 격자에 위치 시키기
def set_golem(x, y, di):
    global cnt, exits

    board[x][y-1:y+2] = [cnt] * 3
    board[x-1][y] = board[x+1][y] = cnt

    cnt += 1    # 다음 골렘
    exits.append([x + dx[di], y + dy[di]])  # 골렘의 출구 저장

정령 이동

정령은 가능한 가장 남쪽으로 이동 한 후, 그 때의 x좌표를 누적해야한다.

bfs를 이용해 움직일 수 있는 칸을 탐색하고, 가장 x좌표가 클때를 누적시킨다.

정령은 골렘 내부 안에서 이동이 가능하며, 출구와인접한 골렘이 있다면 출구를 통해 옮겨갈 수 있다.

주의할 점은 격자를 3칸 늘려놨다는 걸 잊지 않는것..

문제에서 격자의 처음을 1로 지정했기 때문에 늘리기는 3칸 늘렸지만 2를 빼서 맞춰준다.

from collections import deque
# 정령 이동
def move_elf(x, y):
    visited = [[0]*(c+2) for _ in range(r+4)]

    q = deque()
    q.append([x, y])
    visited[x][y] = 1
    max_x = 0

    while  q:
        x, y = q.popleft()
        max_x = max(x, max_x)
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            # 이미 방문함
            if visited[nx][ny] == 1: continue
            # 골렘 안에서 가장 남쪽으로 움직임 / 골렘의 출구로 나가서 인접한 골렘으로 이동
            if (board[nx][ny] == board[x][y]) or (board[nx][ny] > 1 and [x, y] in exits):
                q.append([nx, ny])
                visited[nx][ny] = 1

    return max_x - 2    # 골렘 입장을 위해 늘린만큼 제거/격자 1로 시작

오전에 풀었던 고대 유적 탐사에 비해 간단한 문제라고 느껴졌다.

하지만.. 시험장에서 이 문제를 만났다면 격자 조건 구하느라 진땀 뺐을 거란 나의 예측..

격자를 늘리는 아이디어만 있다면 난이도는 어렵지 않은 문제인듯!

코드

r, c, k = map(int, input().split())
golem = [list(map(int, input().split())) for _ in range(k)]

# 격자 밖으로 나가면 안됨 / 인덱스가 1로 시작 -> 격자 밖(y)을 벽으로 둘러쌈
# 골렘이 격자에 입장하기 전 밖에 있는 모습을 표현하기 위해 x값을 늘려줌 -> 3칸늘림
board = [[1] + [0]*c + [1] for _ in range(r+3)] + [[1]*(c+2)]

# 방향 -> 북동남서(시계)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def move_golem(in_y, di):
    x, y = 1, in_y  # 골렘이 입장 전 상태
    global board
    # 더이상 움직일 수 없을 때 까지
    while True:
        # 남쪽 이동
        # 왼아, 가아, 오아 빈칸
        if sum([board[x+1][y-1], board[x+2][y], board[x+1][y+1]]) == 0:
            x += 1  # 남쪽 이동

        # 서쪽 이동 -> 남쪽 이동
        # 왼위, 왼가, 왼아, 왼왼아, 왼아아 빈칸
        elif sum([board[x-1][y-1], board[x][y-2], board[x+1][y-1], board[x+1][y-2], board[x+2][y-1]]) == 0:
            y -= 1  # 서쪽 이동
            x += 1  # 남쪽 이동
            di = (di - 1) % 4   # 출구 반시계 이동

        # 동쪽 이동 -> 남쪽 이동
        # 오위, 오가, 오아, 오오아, 오아아 빈칸
        elif sum([board[x-1][y+1], board[x][y+2], board[x+1][y+1], board[x+1][y+2], board[x+2][y+1]]) == 0:
            y += 1  # 동쪽 이동
            x += 1  # 남쪽 이동
            di = (di + 1) % 4   # 출구 시계 이동

        # 더이상 이동 불가능
        else:
            break

    return x, y, di

# 골렘이 튀어나갔는지 확인
def is_board(x):
    # x를 늘린 것을 고려해야함 / 골렘의 가운데가 4에 와야 골렘이 모두 안에 위치
    return x < 4

# 골렘 격자에 위치 시키기
def set_golem(x, y, di):
    global cnt, exits

    board[x][y-1:y+2] = [cnt] * 3
    board[x-1][y] = board[x+1][y] = cnt

    cnt += 1    # 다음 골렘
    exits.append([x + dx[di], y + dy[di]])  # 골렘의 출구 저장

from collections import deque
# 정령 이동
def move_elf(x, y):
    visited = [[0]*(c+2) for _ in range(r+4)]

    q = deque()
    q.append([x, y])
    visited[x][y] = 1
    max_x = 0

    while  q:
        x, y = q.popleft()
        max_x = max(x, max_x)
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            # 이미 방문함
            if visited[nx][ny] == 1: continue
            # 골렘 안에서 가장 남쪽으로 움직임 / 골렘의 출구로 나가서 인접한 골렘으로 이동
            if (board[nx][ny] == board[x][y]) or (board[nx][ny] > 1 and [x, y] in exits):
                q.append([nx, ny])
                visited[nx][ny] = 1

    return max_x - 2    # 골렘 입장을 위해 늘린만큼 제거/격자 1로 시작

exits = []  # 골렘 출구를 저장
cnt = 2     # 0: 빈칸, 1: 벽, 2이상: 골렘
result = 0  # 누저 값

# k개의 정령 이동
for in_y, di in golem:
    # 골렘 이동
    x, y , di = move_golem(in_y, di)

    # 골렘이 밖으로 튀어 나갔는지 확인
    if is_board(x):
        # 격자를 초기화
        board = [[1] + [0]*c + [1] for _ in range(r+3)] + [[1]*(c+2)]
        cnt = 2     # 골렘 다 치우기
        exits = []  # 출구 비우기
        continue    # 다음 정령 탐색

    # 골렘 격자에 위치 시키기
    set_golem(x, y, di)

    # 정령 이동

    result += move_elf(x, y)
print(result)

728x90

'프로그래밍 > Python' 카테고리의 다른 글

[SWEA] 2072. 홀수만 더하기 - Python (0)	2024.11.13
[코드트리] 왕실기사의 대결 - 큐 이용 / Python(파이썬) (1)	2024.10.08
[코드트리] 고대 문명 유적 탐사 - Python(파이썬) (0)	2024.09.27
[코드트리] 메이즈 러너 / Python(파이썬) (2)	2024.04.12
[프로그래머스] 퍼즐 조각 채우기 / 깊이/너비 우선 탐색(DFS/BFS) / Python (0)	2024.04.12

NLP 개발 로그

[코드트리] 마법의 숲 탐색 / Python(파이썬)

문제

입력형식

출력 형식

풀이

아이디어

골렘의 이동

골렘 셋팅

정령 이동

코드

'프로그래밍 > Python' 카테고리의 다른 글

댓글

티스토리툴바

[코드트리] 마법의 숲 탐색 / Python(파이썬)

문제

입력형식

출력 형식

풀이

아이디어

골렘의 이동

골렘 셋팅

정령 이동

코드

'프로그래밍 > Python' 카테고리의 다른 글

관련글

댓글

티스토리툴바