제로베이스 20220317

코딩테스트 연습

1. 다각형개수

• 정수 좌표로 이루어진 선분들의 정보를 입력받아 이 선분들의 좌표를 실제로 도화지에 그린다면, 이 그림은 모두 몇 개의 다각형으로 이루어져 있는지를 알려주는 프로그램을 작성하시오.

  

• 여기서 말하는 다각형이란 각 변이 세 개 이상의 직선으로 이루어진 단일폐도형을 말하며, 두 다각형이 겹치게 되면서 생기는 부분에 대한 도형은 다각형으로 인정하지 않는다.

  • 즉, 입력된 좌표로 구성된 선분들만을 이용해서 만들어진 다각형만을 인정한다.

  • 만약 다각형에 그 다각형을 이루지 않는 선분이 연결되어 있으면 다각형이 아니라고 판단한다.

• 예를 들어 입력으로 들어온 선분을 종이 위에 그려봤을 때, 위 그림과 같이 그려졌다면 2가지 다각형이 존재하는 것이고, 답으로 2를 출력하면 된다.

입력

• 첫째 줄에는 선분의 개수 N(1 ≤ N ≤ 60)이 들어온다.

• 다음에는 각 선분의 좌표가 N줄에 걸쳐서 입력으로 들어온다.

• 선분의 좌표는 “(한 쪽 끝점의 가로 좌표, 세로 좌표, 다른 쪽 끝점의 가로 좌표, 세로 좌표)”의 순서로 들어오며, 한 줄에 하나의 선분에 관한 정보가 들어온다. 좌표의 범위는 10,000 이하의 음이 아닌 정수이다.

출력

• 첫째 줄에 다각형의 개수를 출력하시오.

풀이

# your code goes here
 
import sys
 
# 첫째 줄에는 선분의 개수 N(1 ≤ N ≤ 60)이 들어온다.
 
N = int(sys.stdin.readline())
 
# 다음에는 각 선분의 좌표가 N줄에 걸쳐서 입력으로 들어온다. 
 
graph = {} 
 
def p_to_idx(Xi,Yi):
	return str(Xi)+','+str(Yi)
 
 
for _ in range(0,N):
	# (Xi,Yi), (Xj,Yj)의 순서로 들어오며,
	# 한 줄에 하나의 선분에 관한 정보가 들어온다. 
 
	Xi,Yi,Xj,Yj = list(map(int,sys.stdin.readline().split()))
 
	# 각 도형이 다각형을 이루어야 한다 => 각 점에 이어진 선분이 2개 뿐이어야 한다.
	# 다각형에 다각형을 이루지 않는 선이 있을시 인정하지 않는다 => 위와 같음.
 
	p1 = [Xi,Yi]
	p2 = [Xj,Yj]
 
	str1 = p_to_idx(Xi,Yi)
	str2 = p_to_idx(Xj,Yj)
 
	# 그래프 형성
	if str1 not in graph:
		graph[str1] = [p2]
	else:
		graph[str1].append(p2)
 
	if str2 not in graph:
		graph[str2] = [p1]
	else:
		graph[str2].append(p1)
 
 
 
# dfs
 
# 단, 정수 좌표계 위에서 나오는 행동이므로, 점 세개 이상이 같은 직선상에 있다면 도형이 될수 없음
 
def chase_point(v,visited,isfig):
	visited.append(v)
	if len(graph[v]) != 2:
		isfig = False
 
	for point in graph[v]:
		i = p_to_idx(point[0],point[1])
		if not i in visited:
			isfig, visited = chase_point(i,visited,isfig)
 
	return isfig, visited	
 
 
tmp = graph.copy()
cnt = 0
 
 
while(len(graph) > 0):
	flag = False
	isfig, fig = chase_point(next(iter(graph.keys())),[],True)
	for i in range(0,len(fig)):
		del tmp[fig[i]]
 
		# 같은 직선 위에 있다면, 도형이 성립하지 않는다.
		# 적어도 1개 이상의 점이 두 점이 이루는 직선 바깥에 있어야 도형이 성립한다.
		for j in range(i+1,len(fig)):
			if flag == True:
				break
			for k in range(j+1,len(fig)):
				Xi,Yi = list(map(int,(fig[i].split(','))))
				Xj,Yj = list(map(int,(fig[j].split(','))))
				Xk,Yk = list(map(int,(fig[k].split(','))))
				# 기울기 = (x좌표 차이 / y좌표차이)
				# 점 세개로 이루어진 두 직선의 기울기가 다르면, 도형이 성립한다.
 
				# 방어적 코딩 1. 두 점의 Y좌표가 같은 경우, divide by zero 발생.
				# 이 경우, 두 점이 같은 직선상에 있다는 증거이므로 나머지 점 하나가 다르면 무조건 도형 성립. 
				if Yi-Yj == 0:
					if Yk != Yj:
						flag = True
				elif Yj-Yk == 0:
					if Yi != Yj:
						flag = True
 
				elif ((Xi-Xj) / (Yi - Yj)) != ((Xj-Xk) / (Yj - Yk)):
					flag = True
 
	if flag == False:
		isfig = False
 
	if isfig:
		cnt += 1
 
	graph = tmp.copy()
 
 
print(cnt)

채점 결과

• 정답

리뷰

• 처음 보고 다각형 = 간선 두개만 연결된 점들의 집합을 떠올려 그래프로 풀겠다는 판단까지는 맞았다.

• 두번째 함정은 점들이 하나의 직선상에 위치할때, 도형은 성립하지 않는것이다.

  • 이를 위해 기울기를 구해 보정을 실시했다.

• 세번째 함정은 기울기를 구할때 발생한 것으로, 무언가의 차이로 나눌때는 항상 Division by zero를 조심하는것이다.

  • 두 점의 Y좌표가 같다면, 나머지 한점의 Y좌표가 다를때 무조건 도형이 성립한다.
• 그래프에 bfs, 기하학까지 응용해야 하는 문제여서 푸는데 너무 오랜 시간을 사용했다.
  • 빡세게 집중한 시간만 세도 얼추 세시간은 가뿐히 넘긴듯 하다.
• 주요 알고리즘의 구현에 있어 의사 코드를 확실히 알아둘 필요가 있을것 같다.