[백준/2983] 개구리 공주 (Python)

Problem : https://www.acmicpc.net/problem/2983

2983번: 개구리 공주

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 01:03:28

 

---

 

문제 설명

 

트럭을 타고 이동하던 중에 상근이는 휴식을 취하기 위해서 호수에 잠시 들렸다. 호수에는 개구리가 살고 있고, 개구리는 호수 위에 떠있는 식물 N개를 점프하면서 다닌다. 오래된 전설에 따르면 개구리에게 키스를 하면 개구리는 아름다운 공주로 변한다고 한다. 일단 개구리를 잡아야 전설이 사실인지 아닌지 확인할 수 있다. 개구리를 잡아보자.

호수는 2차원 평면으로 생각할 수 있고, 식물은 그 평면 위의 점으로 나타낼 수 있다. (x, y)위에 있는 개구리는 아래 네 가지 방향 중 한 방향으로 점프할 수 있다.

임의의 양의 정수 P에 대해서, (x+P, y+P)로 점프할 수 있다. 이 방향을 A라고 한다.
임의의 양의 정수 P에 대해서, (x+P, y-P)로 점프할 수 있다. 이 방향을 B라고 한다.
임의의 양의 정수 P에 대해서, (x-P, y+P)로 점프할 수 있다. 이 방향을 C라고 한다.
임의의 양의 정수 P에 대해서, (x-P, y-P)로 점프할 수 있다. 이 방향을 D라고 한다.
개구리는 네 방향 중 한 방향을 고른다. 그 다음 그 방향에 있는 가장 가까운 식물로 점프를 한다. 만약, 고른 방향에 식물이 없다면, 개구리는 그 위치에 그대로 있는다. 개구리가 점프를 하고 난 이후에, 원래 있던 식물은 호수로 가라앉게되고 사라진다.

상근이는 식물의 위치와 개구리가 고른 방향을 모두 알고 있다. 상근이는 개구리의 점프가 끝나는 꽃의 좌표를 알아낸 다음, 거기서 개구리를 잡으려고 한다.

개구리의 점프가 끝나는 식물의 위치는 어디일까?

 

입력 및 출력

 

입력

첫째 줄에 식물의 수 N과 점프의 수 K가 주어진다. (1 ≤ N, K ≤ 100,000)

둘째 줄에는 개구리가 고른 방향 K개가 주어진다. 이 방향은 'A','B','C','D'로만 이루어져 있다.

셋째 줄부터 N개 줄에는 식물의 좌표가 X, Y가 주어진다. (0 ≤ X, Y ≤ 1,000,000,000) 처음으로 주어지는 식물에 개구리가 있다.

 

출력

개구리의 점프가 끝나는 식물의 좌표를 출력한다.

 

입력 예시

 

7 5
ACDBB
5 6
8 9
4 13
1 10
7 4
10 9
3 7

 

출력 예시

 

7 4

 

 

---

 

풀이

 

100000개의 조건을 만족하는 노드를 단순하게 저장하고 탐색하면 분명한 시간 초과를 겪게 된다. 탐색의 최악 시간 복잡도는 O(N)이므로 최악의 경우 100000^2의 연산이 필요하다.

 

즉, 임의의 방향 'A', 'B', 'C', 'D'에 대해 가장 인접한 노드를 O(1)의 시간 안에 찾아낼 수 있으며, 삭제 연산 역시 O(1)이 소모되는 자료구조가 필요하다. 정답을 말하자면, 링크드리스트가 되겠다!

 

방향 이동이 모두 대각선 방향이므로, 두 번의 정렬(x-y, x+y를 기준으로)로 N개의 식물 노드들을 정렬하고, 조건을 만족하는 두 노드(정렬 기준인 x-y가 같은 경우 = 같은 대각선이 있는 경우) 이중으로 연결해주면 된다.

 

탐색 시에는 진행 가능한 경우에 한해 다음 노드를 갱신하고, 현재 노드를 4방위로 삭제하는 연산을 시행하면 된다!

 

 

링크드리스트를 활용하는 문제는 흔치 않았는데, 오랫만에 복습 겸 풀어볼 기회가 되어 기쁘다.

 

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

class Node:
  def __init__(self, x, y):
    self.x = x
    self.y = y
    self.dir = {
      'A' : None,
      'B' : None,
      'C' : None,
      'D' : None
    }

def init() :
  N, K = map(int, input().split())
  node_list = list()
  move_string = input().strip()

  for i in range(N) :
    x, y = map(int, input().split())
    node = Node(x, y)
    if i == 0:
      start = node
    node_list.append(node)

  node_list.sort( key = lambda nd : (nd.x - nd.y, nd.x))
  for i in range(1, N) :
    if node_list[i-1].x - node_list[i-1].y == node_list[i].x - node_list[i].y :
      node_list[i-1].dir['A'] = node_list[i]
      node_list[i].dir['D'] = node_list[i-1]

  node_list.sort( key = lambda nd : (nd.x + nd.y, nd.x))
  for i in range(1, N) :
    if node_list[i-1].x + node_list[i-1].y == node_list[i].x + node_list[i].y :
      node_list[i-1].dir['B'] = node_list[i]
      node_list[i].dir['C'] = node_list[i-1]

  return move_string, start
  
def remove(node, s1, s2) :
  if node.dir[s1] is not None and node.dir[s2] is not None :
    node.dir[s1].dir[s2], node.dir[s2].dir[s1] = node.dir[s2], node.dir[s1]
  elif node.dir[s1] is not None :
    node.dir[s1].dir[s2] = None
  elif node.dir[s2] is not None :
    node.dir[s2].dir[s1] = None

def jumps(move_string, node) :
  for s in move_string :
    if node.dir[s] is not None :  
      next_node = node.dir[s]
      remove(node, 'A', 'D')
      remove(node, 'C', 'B')
      node = next_node
      
  print(node.x, node.y)
  

def solve() :
  move_string, start = init()
  jumps(move_string, start)

solve()

풀이 완료~