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

문제 설명

좌표계에 네잎클로버가 흩어져있고 명령에 따라 움직이면서 가장 가까운 네잎클로버를 만나면 멈추고 다음 명령에 따라 움직여 최종 위치를 도출해내는 문제

코드

import sys
input = sys.stdin.readline 
from collections import defaultdict
from bisect import bisect_left, bisect_right

n, m = map(int, input().split())
dict_x = defaultdict(list)
dict_y = defaultdict(list)

for _ in range(n):
    x, y = map(int, input().split())
    dict_x[x].append(y)
    dict_y[y].append(x)

for key in dict_x:
    dict_x[key].sort()
for key in dict_y:
    dict_y[key].sort()

cmds = input().rstrip()

x = y = 0
for cmd in cmds:
    if cmd == "L":
        x = dict_y[y][bisect_left(dict_y[y], x) - 1]
    elif cmd == "R":
        x = dict_y[y][bisect_right(dict_y[y], x)]
    elif cmd == "U":
        y = dict_x[x][bisect_right(dict_x[x], y)]
    elif cmd == "D":
        y = dict_x[x][bisect_left(dict_x[x], y) - 1]

print(x, y)

풀이

100만년만에 알고리즘 문제풀이 포스팅인것 같다..

3주전 부터 dkt 대회가 있었어가지고 신경쓰지 못했다.

오늘 포스팅할 문제는 알고리즘 스터디때 못푼 문제이다.(스터디원분의 코드를 참고하여 다시 풀어봄!)

그리고 내가 그동안 해온 알고리즘 포스팅들을 봤는데 문제에 대한 설명부분이 없어서 나조차도 이게 무슨 문제인지 기억이 안나서 문제 설명 부분을 제일 위에다가 추가했다. 앞으로도 계속 이런식으로 쓸 예정

이번 문제는 명령의 최대 개수가 100000이고 네잎클로버 최대 개수도 100000이기때문에 단순한 탐색으로는 무조건 시간초과가 난다.

이분탐색을 써야하는 문제이고 탐색을 좌표별로 해줘야한다.

x좌표로 먼저 설명을 하면 각각의 x좌표에 대해서 key 값을 해당 x좌표로 하고 연결된 y좌표들을 value로 하는 dictionary를 구성해준다. y좌표에 대해서도 동일하게!

이분탐색을 할 것이므로 value들을 정렬해준다.

현재 위치에 대해서 bisect 모듈의 bisect_left, bisect_right 함수를 이용해 왼쪽, 아래쪽으로 갈 때에는 bisect_left를 이용해서 가장 가까운 다음 위치를 찾아주고(작은쪽을 찾아줘야 하니깐) 오른쪽, 위쪽으로 갈 때에는 bisect_right를 이용해 찾아준다.

이때 bisect_left에서는 -1 을 해줘야하는데 이유는 다음과 같다.

예를 들어 list = [10, 11, 15, 17, 19] 라는 배열이 있고 현재 15이고 11을 찾아야 하면 bisect_left(list, 15)를 해주는데 이때 반환값은 2가 나온다.

bisect_left함수는 해당 원소가 들어갈 가장 작은 index를 반환해주는 함수이기 때문에 그렇다.

우리가 얻고싶은 값은 11(index 1)이기 때문에 1을 빼주어 값을 찾아준다.

이번 문제를 통해 defaultdict와 bisect에 대해 좀 더 깊게 이해하는 시간을 가졌다.