백준 3089 네잎 클로버를 찾아서

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/3089

이 문제는 2차원 좌표 상에서 (0, 0)을 시작으로 상하좌우로 이동하면서 좌표 상에 네잎클로버를 찾아가는 문제이다.

풀이

난이도 : GOLD III

이 문제를 처음보았을 때, 이분탐색을 사용하여 네잎클로버의 좌표들을 찾아야겠다고 생각하였다.

처음 시도는 x,y 좌표를 모두 입력받고, x 좌표 기준으로 정렬한 x_alien list 와 y 좌표를 기준으로 정렬한 y_alien list 를 사용하고자 하였다.
하지만, 이 방법으로 하면 한 번 이동하고자 할 때, 두 번의 이분탐색을 해야 했기 때문에 방법을 바꾸게 되었다.

다음으로 시도한 방법은 해쉬-맵 자료구조를 사용한 방법이다. 파이썬에는 key-value 자료구조를 dictionary로 사용할 수 있다.
따라서 value 값으로 list를 가지도록 dictionary를 구성하였다.

예)
x_alien = {0 : [-1, 0], 1 : [2, 3], 2: [1]}
-> x가 0일 때 y는 -1, 0의 값을 가질 수 있다.

y_alien = {-1 : [0], 0 : [0], 1 : [2], 2 : [1], 3 : [2]}
-> y가 -1일 때 x는 0의 값을 가질 수 있다.

위 예제와 같은 방식으로 x좌표, y좌표 기준으로 나누어 정보를 저장해두었다.
이후에 상하좌우로 움직이는 명령을 아래와 같이 수행하였다.

1) 위, 아래로 움직이는 경우는 x좌표는 고정하고 y좌표만 이동하면 되기 때문에 x_alien에서 x값을 key로 갖는 value list에서 해당하는 y좌표를 이분 탐색으로 찾는다.
2) 좌, 우로 움직이는 경우는 y좌표는 고정하고 x좌표만 이동하면 되기 때문에 y_alien에서 y값을 key 로 갖는 value list에서 해당하는 x좌표를 이분 탐색으로 찾는다.

예)
(0, 0) 에서 아래로 이동하기
x_alien[0] 정보(value)를 가져옴 : [-1, 0]
이분 탐색으로 (0, 0)의 다음 y 좌표를 찾기 : -1
현재 좌표에 반영 : (0, -1)

코드

from bisect import bisect_left, bisect_right
import sys

# key, value dict (x 기준, y 기준)
n, m = map(int, sys.stdin.readline().split())
x_aliens, y_aliens = {}, {}

# x 좌표 y 좌표에 따라 x_aliens, y_aliens의 value로 list 구성
for _ in range(n):
    x, y = map(int, sys.stdin.readline().split())
    if x_aliens.get(x):
        x_aliens[x].append(y)
    else:
        x_aliens[x] = [y]

    if y_aliens.get(y):
        y_aliens[y].append(x)
    else:
        y_aliens[y] = [x]

commands = str(input())

# 이분 탐색을 위해 각 value list 정렬
for key, value in x_aliens.items():
    x_aliens[key] = sorted(value)
for key, value in y_aliens.items():
    y_aliens[key] = sorted(value)

# 현재 x, y를 이동시키며 최종 x, y를 결과로 출력
current_x, current_y = 0, 0
for command in commands:
    if command == "U":
        # UP, x 좌표는 고정이므로 x_aliens에서 current_x를 key로 가지는 value list에서 다음 y 좌표를 찾음
        current_y = x_aliens[current_x][bisect_right(x_aliens[current_x], current_y)]
    elif command == "D":
        # DOWN, "U"와 마찬가지로 찾지만 bisect_left를 사용하여 왼쪽에 있는 값을 다음 y 좌표로 지정
        current_y = x_aliens[current_x][bisect_left(x_aliens[current_x], current_y) - 1]
    elif command == "R":
        # RIGHT, y 좌표는 고정이므로 y_aliens에서 current_y를 key로 가지는 value list에서 다음 x 좌표를 찾음
        current_x = y_aliens[current_y][bisect_right(y_aliens[current_y], current_x)]
    elif command == "L":
        # LEFT, "R"과 마찬가지로 찾지만 bisect_left를 사용하여 왼쪽에 있는 값을 다음 x 좌표로 지정
        current_x = y_aliens[current_y][bisect_left(y_aliens[current_y], current_x) - 1]

print(current_x, current_y)