[구름톤 챌린지] 4주차 18일차 중첩 점

 

 

문제

---

한 변의 길이가 $N$인 정사각형이 있다. 플레이어는 이 정사각형 위에 $M$개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세려고 한다. 플레이어가 반직선을 그리는 과정은 아래와 같다.

 

 

1. 반직선을 그리기 시작할 칸 $(y, x)$를 정한다. $(y, x)$는 주어진 정사각형을 $1 \times 1$ 크기의 정사각형으로 나눴을 때, $y$번째 행의 $x$번째 열에 해당하는 칸이다.
2. 반직선을 그릴 방향 $d$를 정한다. 방향은 상하좌우 중 하나이며, 항상 정사각형 테두리의 가로 혹은 세로와 평행하다.
3. 반직선을 그린다. 반직선은 항상 시작 칸의 테두리에서부터 시작하며, 같은 칸을 지나는 평행한 직선이 서로 만나지 않도록 그린다.

아래 그림은 길이가 $4$인 정사각형 위에 다음 세 개의 직선을 그린 그림이다.

 

 

• $(3,2)$, 오른쪽 / $(3,3)$, 왼쪽 / $(3,2)$, 위쪽

$(3,2)$ 칸과 $(3,3)$ 칸을 지나는 두 개의 가로 반직선이 있지만, 두 반직선은 서로 평행하기 때문에 중첩 점이 생기지 않는다. 그러나 $(3,2)$ 칸을 지나는 세로 반직선과 두 반직선은 교차하므로 결과적으로는 두 개의 중첩 점이 생긴다.

플레이어가 모든 반직선을 그린 뒤 생기는 중첩 점의 개수를 구해보자.

입력

---

첫째 줄에 정사각형의 크기 $N$과 그리려는 반직선의 개수 $M$이 공백을 두고 주어진다.
다음 $M$개의 줄에는 플레이어가 그을 반직선의 정보를 나타내는 $y_i, x_i, d_i$가 공백을 두고 주어진다. $(y_i, x_i)$ 칸에서 시작해 $d_i$ 방향으로 반직선을 긋는다는 의미이다.

 

 

• $1 \leq N \leq 100$
• $1 \leq M \leq 100 \ 000$
• $1 \leq x_i, y_i \leq N$
• $d_i$는 U, D, L, R 의 네 문자 중 하나이다. 각각 상하좌우 방향을 의미한다.

출력

---

모든 반직선을 그렸을 때, 중첩 점의 개수를 출력하시오.

 

---

문제 접근 방식

---

누적 합 알고리즘의 응용인 imos법을 사용하였다.

 

우리는 가로 선(혹은 세로선)이 해당 구역에 몇개 그어져 있는지 나타내는 $2$차원 배열을 만드는 것이 우리의 목적이다.

 

하지만, 이를 $N$의 범위는 최대 $100$이고, 만약 쿼리의 개수의 최댓값은 $100,000$이기 때문에, 이 배열을 그대로 누적 합으로 나이브하게 구현하려고 한다면 쿼리 한번 당 $O(N)$, 즉, $O(NM)$의 시간 복잡도가 소요된다.

 

따라서 이를 방지하기 위해 개수의 증감만 표시를 해주는 imos배열을 구현해주었다.

 

imos배열을 다 채우는데에 소요되는 시간 복잡도는 $O(M)$이다.

 

이후 이 $imos$배열을 원 상태의 누적 합 배열(가로선 혹은 세로선이 해당 구역에 몇개 그어져 있는지 나타내는 배열)로 복구하는데에 소요되는 시간 복잡도는 $O(N^2)$이다.

 

따라서, $O(M + N^2)$의 시간 복잡도로, 이는 $O(NM)$의 시간 복잡도보다 적게 소요가 된다.

 

그렇게 만든 가로선 배열과 세로선 배열의 각 원소를 서로 곱하면, 이는 곧 가로선과 세로선이 만나는 교차점의 개수가 되므로, 이를 전부 더하면 우리가 구하고자 하는 값이 나온다.

 

나의 경우 세로선 배열을 구현할 때 imos를 세로로 적용하는 거나 복원하도록 구현하기가 조금 까다로워서, 세로선 배열을 $90$도 돌린 배열을 구현했고, 이후 곱할 때 인덱스의 앞뒤를 뒤집어서 곱하도록 구현해주었다.

 

---

정답 코드

---

# 중첩 점
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
# imos 배열
vertical_imos = [[0 for _ in range(N+1)] for _ in range(N)]
horizontal_imos = [[0 for _ in range(N+1)] for _ in range(N)]
for _ in range(M):
    y, x, d = input().rstrip().split()
    y, x = int(y)-1, int(x)-1
    if d == 'L':
        horizontal_imos[y][0] += 1
        horizontal_imos[y][x+1] -= 1
    elif d == 'R':
        horizontal_imos[y][x] += 1
        horizontal_imos[y][N] -= 1
    elif d == 'U':
        vertical_imos[x][0] += 1
        vertical_imos[x][y+1] -= 1
    else:
        vertical_imos[x][y] += 1
        vertical_imos[x][N] -= 1
# 누적 합 복원
vertical_line = [[0 for _ in range(N)] for _ in range(N)]
horizontal_line = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    V, H = vertical_imos[i][0], horizontal_imos[i][0]
    for j in range(N):
        vertical_line[i][j] = V
        horizontal_line[i][j] = H
        V += vertical_imos[i][j+1]
        H += horizontal_imos[i][j+1]
# 중첩 점 구하기
total_dots = 0
for i in range(N):
    for j in range(N):
        dots = horizontal_line[i][j]*vertical_line[j][i]
        total_dots += dots
print(total_dots)

 

---

특별히 배운 점

---

누적 합의 응용 개념을 다질 수 있어서 좋은 문제였던 것 같다. 다른 풀이로는 세그먼트 트리나 DP로 하는 풀이가 있다고 했는데 이건 해설을 봐야 알 수 있을 것 같다.