Problem

문제 설명

2차원 배열에서 각 칸의 중첩 점 개수를 계산한다.
1. 선분의 시작 칸과 종료 칸까지 각 칸마다 변화된 직선의 개수를 센다. 이때 선분의 최대 개수(M) 100,000 x 칸의 최대 범위(N) 100이므로 시간 제한에 걸리지 않는다.
2. 2차원 배열을 한 칸씩 확인하며 중첩 점 개수(= 가로 직선 개수 x 세로 직선 개수)를 계산한다. 마찬가지로 칸의 최대 개수(N2) 10,000이므로 시간 제한에 걸리지 않는다.

Submitted Code

Python

 1 N, M = map(int, input().split())
 2
 3 board = [[(0, 0)] * N for _ in range(N)]
 4 dirs = {'R': (0, 1), 'L': (0, -1), 'D': (1, 0), 'U': (-1, 0)}
 5 for _ in range(M):
 6     y, x, d = input().split()
 7     y, x = map(lambda i:int(i) - 1, (y, x))
 8     dy, dx = dirs[d]
 9     while 0 <= y < N and 0 <= x < N:
10         hor, ver = board[y][x]
11         board[y][x] = (hor + abs(dx), ver + abs(dy))
12         y += dy
13         x += dx
14
15 points = 0
16 for i in range(N):
17     for j in range(N):
18         hor, ver = board[i][j]
19         points += hor * ver
20 print(points)

Line 1

정사각형의 크기 N과 선분의 개수 M을 입력받는다.

Line 3

정사각형의 각 칸에 (가로 선분의 개수, 세로 선분의 개수)를 0으로 초기화한다.

Line 4

선분을 그릴 방향 d에 대해 (dy, dx)를 설정한다.

Line 5

선분의 개수만큼 for문을 반복한다.

Line 6-8

선분의 시작점 (y, x)을 int 자료형으로 입력받는다. 선분의 방향 d을 str 자료형으로 입력받고, dirs에 설정한 (dy, dx)를 불러온다.

Line 9

(y, x)가 정사각형 안에 있는 동안 while문을 반복한다.

Line 10-11

선분이 그려지는 칸의 (가로 선분의 개수, 세로 선분의 개수)을 (hor, ver)에 저장한다.
가로 선은 행(x축)에 대해 평행하게 이동할 때(dy = 0), 세로 선은 열(y축)에 대해 평행하게 이동할 때(dx = 0) 그려진다. 따라서

• 가로 선분의 개수 = 기존 선분 개수 hor + 새로 그리는 선분 개수 abs(dx)
• 세로 선분의 개수 = 기존 선분 개수 ver + 새로 그리는 선분 개수 abs(dy)

Line 12-13

정사각형의 칸 (y, x)을 (dy, dx)만큼 업데이트한다.

Line 15-19

중첩 점의 총합 points를 0으로 초기화한 후, 정사각형의 칸을 하나씩 확인하면서 points를 업데이트한다.

Line 20

중첩 점의 총합 points을 출력한다.