[구름톤 챌린지 #18] 중첩 점

문제18. 중첩 점

구름LEVEL

---

---

문제 해결 방법

문제의 구현 난이도 자체는 높지 않지만, 무엇을 구현해야 할지에 대한 아이디어를 생각해내는데 조금 시간이 걸리는 문제였다. 우선, 해결책을 비교적 간단하게 떠올릴 수 있도록 단계별로 아이디어를 떠올려보았다.

1. 두 직선이 한 칸에서 중첩이 되려면? 상하 방향으로 뻗은 직선과 좌우로 뻗은 직선이 만나면 중첩이 된다. 상하 방향 직선끼리, 혹은 좌우 방향 직선끼리 만나서는 중첩이 될 수 없다.
2. 해당 칸을 지나가는 직선들의 수를 알고 있을 때, 해당 칸의 중첩 점의 개수를 알 수 있나? 상하 방향의 직선의 개수와 좌우 방향의 직선의 개수를 곱한 값이 해당 칸의 중첩 점의 개수이다.

이렇게 아이디어를 정리하면 구현 방법을 떠올리는 것은 어렵지 않다. 각 칸에 대한 정보를 담을 2차원 배열을 만들고, 그 칸 내부에는 해당 칸을 지나가는 상하 직선의 수와 좌우 직선의 수를 저장한다. 모든 입력값에 대해 2차원 배열의 정보를 업데이트 한 다음, 마지막에는 전체 배열을 돌면서 각 칸의 중첩 점의 개수를 모두 더하면 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys
n, m = map(int, sys.stdin.readline().split())

arr = [[[0,0] for i in range(n+1)] for j in range(n+1)]

direction_mapper = {"U": -1, "D": 1, "L": -1, "R": 1}

def draw_line(input_list):
	global arr, direction_mapper
	
	y, x, direction = input_list.split()
	y = int(y)
	x = int(x)
	d = direction_mapper[direction]
	
	#상하 직선이라면
	if direction == "U" or direction == "D":
		while 0 < y < n+1:
			arr[y][x][0] += 1
			y += d
	#좌우 직선이라면
	else:
		while 0 < x < n+1:
			arr[y][x][1] += 1
			x += d
	
	
for i in range(m):
	draw_line(sys.stdin.readline())

result = 0
for i in range(1, n+1):
	for j in range(1, n+1):
		result += arr[i][j][0] * arr[i][j][1]

print(result)