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

2024 상반기 오후 1번 문제로 나왔던 '마법의 숲 탐색' 문제의 python 풀이입니다. 

1. 문제 링크

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

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

 

2. 한줄평

시뮬레이션 문제의 경우 시간초과가 나는 경우가 거의 없었는데 시간 초과가 나서 도대체 뭐가 문제일까 고민했는데 치명적인 실수를 했더라구요..

저의 경우 가장 깊은 행을 구할 때 dfs를 사용했는데 1->2->3으로 가든 1->3으로 가든 가장 깊은 곳의 열만 알면 되니까 방문한 곳의 visited_map을 다시 백트레킹 할 필요가 없었는데 해버려서 필요없는 경우까지 과하게 탐색한거였어요

문제의 성격을 잘 파악해서 visited_list를 백트레킹해야하는지 안해야하는지도 신중하게 결정해야할것 같습니다.

(문제 유형 자체는 bfs로 되어있긴하던데 bfs로 풀든 dfs로 풀든 큰 상관은 없을것 같아요. bfs로 풀었으면 visited_list를 올바르게 업데이트 했을 것 같긴하네요)

 

3. 풀이

case_1_check_list = [(1, -1), (2, 0), (1, 1)]
case_2_check_list = [(-1, -1), (0, -2), (1, -2), (1, -1), (2, -1)]
case_3_check_list = [(-1, 1), (0, 2), (1, 2), (1, 1), (2, 1)]

R, C, K = map(int, input().split())
board = [[-1]* C for _ in range(R)]

center_position_list = []
direction_list = []
for i in range(K):
    c, d = map(int, input().split())
    center_position_list.append((-2, c-1))
    direction_list.append(d)

in_board_list = []

dx = [-1, 0, 1, 0] # 북동남서가 기본
dy = [0, 1, 0, -1]

def position_update(idx, next_center):
    global board, center_position_list
    cur_x, cur_y = center_position_list[idx]
    # 기존꺼 다 0으로
    if cur_x >= 0:
        board[cur_x][cur_y] = -1
    for i in range(4):
        if cur_x+dx[i] >=0:
            board[cur_x+dx[i]][cur_y+dy[i]] = -1

    new_x, new_y = next_center
    if new_x >= 0:
        board[new_x][new_y] = idx
    for i in range(4):
        if new_x + dx[i] >= 0:
            board[new_x+dx[i]][new_y+dy[i]] = idx

    center_position_list[idx] = (new_x, new_y)

def case_check(idx, case_num):

    center_x, center_y = center_position_list[idx]
    if case_num == 1:
        check_list = case_1_check_list
    elif case_num ==2:
        check_list = case_2_check_list
    elif case_num ==3:
        check_list = case_3_check_list

    for i in range(len(check_list)):
        dx, dy = check_list[i]
        check_x, check_y = center_x+dx, center_y + dy

        if check_x < 0:
            continue

        elif 0<=check_x<R and 0<=check_y<C:
            if board[check_x][check_y] == -1:
                continue
            else:
                return False
        else:
            return False
    return True

def get_door_position(idx):
    center_x, center_y = center_position_list[idx]
    dir = direction_list[idx]
    door_x, door_y = center_x+dx[dir], center_y+dy[dir]
    return (door_x, door_y)

def can_move(from_idx, to_idx): # 둘다 보드에 있다고 가정하고 돌리는거임
    from_door_position = get_door_position(from_idx)
    to_center_position = center_position_list[to_idx]

    x_difference = abs(from_door_position[0] - to_center_position[0])
    y_difference = abs(from_door_position[1] - to_center_position[1])

    if x_difference + y_difference == 2:
        return True

def case_move(idx, case_num):
    current_x, current_y = center_position_list[idx]
    if case_num == 1:
        position_update(idx, (current_x+1, current_y))
    elif case_num ==2:
        position_update(idx, (current_x+1, current_y-1))
        direction_list[idx] = (direction_list[idx]-1+4)%4
    elif case_num ==3:
        position_update(idx, (current_x+1, current_y+1))
        direction_list[idx] = (direction_list[idx] + 1) % 4
def one_simulation(idx):
    global in_board_list, board
    while(True):
        if case_check(idx,1):
            case_move(idx, 1)
        elif case_check(idx, 2):
            case_move(idx, 2)

        elif case_check(idx, 3):
            case_move(idx, 3)
        else:
            break


    if center_position_list[idx][0] < 1:
        in_board_list = []
        board = [[-1] * C for _ in range(R)]

        return -1

    else:
        # 정령이 가장 깊이 갈 수 있는 곳 구해야함
        most_deep_idx = idx
        visited_list = [False] * len(in_board_list)

        def get_move_deep(current_idx):
            nonlocal most_deep_idx
            current_center = center_position_list[current_idx]
            most_deep_center = center_position_list[most_deep_idx]
            if current_center[0] > most_deep_center[0]:
                most_deep_idx = current_idx

            for i in range(0, len(in_board_list)):
                to_index = in_board_list[i]
                if visited_list[i] == False and can_move(current_idx, to_index):
                    visited_list[i] = True
                    get_move_deep(to_index)

        get_move_deep(idx)
        in_board_list.append(idx)
        return center_position_list[most_deep_idx][0]+1




total = 0
for i in range(K):
    one = one_simulation(i)
    total += (one+1)

print(total)