삼성 SW 역량 테스트 : 구슬 탈출 2 (백준 13460번)

해당 문제는 백준에서 제공된 기출 문제입니다.

[문제 설명 및 파악]

13460번: 구슬 탈출 2

일단 이 문제의 요구사항과 힌트 및 접근 방식에 대해서 알아보자. 해당 문제는 결국 중력을 이용해서 이리 저리 굴려 파란공이 구멍에 빠지지 않도록 빨간공을 빼내는 것이다. 물론 많은 제한과 여러 조건들이 있지만, 이는 코드 설명 시 언급하겠다. 그렇다면 어떻게 접근해야 될까? 이 문제도 결국 모든 경우를 알아야 한다. 현재 위치에서 갈 수 있는 모든 방향에 대해서 고려하여 이동 후 또 다시 모든 방향에 대해서 고려하여 이동한다. 즉, BFS이다. 하지만 이 문제가 더욱이나 어려운 이유는 두가지의 공 모두가 동시에 움직이며 심지어 겹쳐서는 안된다는 것이다. 나는 이 부분을 어떻게 처리해야할지 고민하다 결국 풀지 못했다. 이에 대한 설명은 코드에 실어 놓았다. 마지막으로 BFS는 내가 이미 탐색했던 경로는 다시 탐색하지 않게 설정해주는 것이 시간복잡도를 줄이기 위해서 거의 필수이다. (설정하지 않으면 굉장히 느림) 이런 조건들과 방법들을 이용해서 코드를 구현해보겠다.

from collections import deque

#      ↑, →, ↓, ←
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]


# 현재 R,B의 위치 파악
def find_loc(game_map):
    loc = {}
    for i in range(len(game_map)):
        for j in range(len(game_map[0])):
            if game_map[i][j] == 'R':
                loc['R'] = [i, j]
            elif game_map[i][j] == 'B':
                loc['B'] = [i, j]
    return loc


# 이동할 수 있는 만큼 (벽이나 목표지점에 도달할때까지) 움직인 후의 위치 반환
def as_far_as_possible(y, x, d):
    next_y = y + dy[d]  # 다음 이동할 위치_row
    next_x = x + dx[d]  # 다음 이동할 위치_col
    move_cnt = 0  # 얼만큼 이동했는지 파악 (추후의 R과B의 이동횟수에 따른 처리를 위해)
    while game_map[y + dy[d]][x + dx[d]] != '#' and game_map[y + dy[d]][x + dx[d]] != '0':  # 다음위치가 벽이나 목표지점이 아닐때까지 이동
        y += dy[d]
        x += dx[d]
        move_cnt += 1
    return y, x, move_cnt


def only_red_marble(game_map):
    n, m = len(game_map), len(game_map[0])
    # 이미 탐색한 경로였다면 배제하기 위해 visted(4차원_R과B의 row,col 모두를 저장하기 위해) 설정
    visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
    loc = find_loc(game_map)  # 시작할때의 위치를 파악
    r_y, r_x = loc['R']  # R의 위치 저장
    b_y, b_x = loc['B']  # B의 위치 저장
    queue = deque()  # BFS사용을 위한 queue설정
    queue.append((r_y, r_x, b_y, b_x, 1))  # 현재위치에서 BFS 시작, turn은 1부터
    visited[r_y][r_x][b_y][b_x] = True  # 현재위치에 대해서 다시 반복하지 않기 위해서 기록
    while queue:  # 위치를 순차적으로
        r_y, r_x, b_y, b_x, turn = queue.popleft()  # 큐를 이용해 FIFO
        if turn > 10:  # 턴이 10 이하여야 함
            break
        for d in range(4):  # 모든 방향에 대해서 탐색
            # 해당 방향에 대해서 갈 수 있을 만큼 이동
            next_r_y, next_r_x, r_cnt = as_far_as_possible(r_y, r_x, d)  # R에 대해서 구함
            next_b_y, next_b_x, b_cnt = as_far_as_possible(b_y, b_x, d)  # B에 대해서 구함

            # 해당 방향에 대해서 갈 수 있을 만큼 이동한 후의 다음 위치에 대한 판단
            if game_map[next_b_y][next_b_x] == 'O':  # B가 목적지에 도달하면 안되므로
                continue  # 그냥 배제한다는 뜻. 더 들어가지 않는다!
            if game_map[next_r_y][next_r_x] == 'O':  # B가 목적지에 도달하지 않은 채 목적지에 R이 도달하면
                return True  # 원하는 상황이므로 True 반환
            if next_r_y == next_b_y and next_r_x == next_b_x:  # 목적지가 아닌 벽에 도달했는데 R과B의 위치가 같을 경우
                # 각각의 이동거리를 비교하여 처리 (더 많이 이동한 구슬이 뒤로 가야됨)
                if r_cnt > b_cnt:  # r이 더많이 이동했다면
                    next_r_y -= dy[d]  # r의 위치를 한칸 전으로
                    next_r_x -= dx[d]
                else:
                    next_b_y -= dy[d]
                    next_b_x -= dx[d]

            # 이미 탐색한 경우라면 배제하기 위한 코드 (시간복잡도를 줄이기 위함)
            if not visited[next_r_y][next_r_x][next_b_y][next_b_x]:  # R과 B 모두의 위치를 고려하여 이미 탐색하지 않은 경우라면
                visited[next_r_y][next_r_x][next_b_y][next_b_x] = True  # 해당 위치를 방문했다고 기록
                queue.append((next_r_y, next_r_x, next_b_y, next_b_x, turn + 1))  # 이 위치를 기준으로 다시 탐색하기 위해 queue에 저장

    return False  # turn이 10번이 넘어가면 실패이므로 False 반환

이 문제는 결국 R과B를 동시에 움직이는 것을 어떻게 처리하며 visited와 같이 이미 탐색한 경로를 어떻게 처리해 줄지가핵심인 것 같다. visited같은 경우 r만의 위치만을 기록하여 방문여부를 판단하는 것이 아니라 r과b가 동시에 움직이기 때문에 r과b의 위치 모두를 기록해줘야한다는 점이 까다로웠던 것 같다.

---

[잘못된 풀이]

일단 R과B를 동시에 고려하지 않고 R을 기준으로 B를 상대적으로 생각하고 접근한 것이 잘못됐었다. 애초에 R을 먼저 처리하고 B를 처리하는 것은 동시에 움직인다는 것을 고려하지 않은 것이다. 또한 visited와 같이 이미 탐색한 경로를 처리해줄 생각은 했지만 이를 r과b의 모든 위치를 기록하며 판단할 생각은 못했다. 여러모로 푸는데 걸림돌이 많았던 것 같다.

---

[마무리]

결론적으로 이 문제는 굉장히 어려웠다. 접근방식을 생각해내기도 어렵고, 접근방식을 생각해 냈다고 해도 까다로운 조건들이 좀 많아서 풀어내는데 걸림돌이 굉장히 많았던 것 같다. 또한, 구현자체도 쉽지는 않았다... 처음 풀었을 때는 1시간 반정도 투자해도 못풀었고, 두번째 풀었을 때는 1시간반을 투자하여 풀었어도 visited구현에 막혀서 시간초과가 됐다. 난이도는 굉장히 어려웠지만, 이 문제를 통해서 배운것이 많았던 것 같다.