[구름톤 챌린지] 4주차_ 16~ 18일차 학습

Day16 연합 - 구름LEVEL (goorm.io)

내 풀이 과정

지난주에 배운 지식을 통해 그래프를 이용해 풀수 있게되었다

응용문제다 보니 크게 어려운점은 없었다 갔다가 돌아올 수 있는가를 확인하여 연합의 수를 카운트 해주었다.

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
from collections import deque

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
checked = [0]*(N+1)
for _ in range(M):
	s, e = map(int, input().split())
	graph[s].append(e)
result = 0

for i in range(1, N+1):
	if not checked[i]:
		q = deque([i])
		result +=1
		checked[i] = 1
		while q:
			now = q.popleft()
			for scan in graph[now]:
				if not checked[scan] and now in graph[scan]:
					q.append(scan)
					checked[scan] = 1

print(result)

 

정해 코드

내 코드와 크게 다른점은 없어보였다

 

from collections import deque

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)
result = 0

for _ in range(M):
	s, e = map(int, input().split())
	graph[s].append(e)

for i in range(1, N + 1):
	if visited[i]:
		continue
	
	q = deque([i])
	result += 1
	visited[i] = 1
	
	while q:
		now = q.popleft()
		for to in graph[now]:
			if not visited[to] and now in graph[to]:
				q.append(to)
				visited[to] = 1
	
print(result)

Day17 그래프의 밀집도 - 구름LEVEL (goorm.io)

내 풀이 과정

컴포넌트의 밀도를 구하기위해 머리를 굴리다보니 상당히 복잡해보이는 코드가 작성되었다.

머릿속에 있는걸 직관적으로 작성해낼 수 있다면 얼마나 좋을까 멍청한 내가 싫다..

 

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean

from collections import deque

N, M = map(int, input().split())
computer = [[] for _ in range(N+1)]
checked = [0]*(N+1)
listMildo = []

for _ in range(1, M+1):
	a, b = map(int, input().split())
	computer[a].append(b)
	computer[b].append(a)
	
comgroup = 0

for i in range(1, N+1):
	componentMix = set()
	comCount = 0
	if not checked[i]:
		q = deque([i])
		comgroup +=1
		checked[i] = comgroup
		while q:
			now = q.popleft()
			comCount += 1
			for scan in computer[now]:
				if now in computer[scan]:
					listsort = sorted([now, scan])
					componentMix.add(str(listsort[0])+str(listsort[1]))
				if not checked[scan] and now in computer[scan]:
					q.append(scan)
					checked[scan] = comgroup
	if comCount > 0:			
		listMildo.append(len(componentMix)/comCount)
		
idx = listMildo.index(max(listMildo))+1
res = list(filter(lambda x: checked[x] == idx, range(len(checked))))

print(*res)

정해 코드

정해코드를 보면 항상 더깔끔한 것 같다.

from collections import deque

def bfs(start):
	q = deque([start])
	component = set()
	
	while q:
		now = q.popleft()
		
		if visited[now]:
			continue
		
		visited[now] = 1
		component.add(now)
		
		for to in graph[now]:
			if not visited[to]:
				q.append(to)
	
	edge = 0
	
	for i in component:
		for to in graph[i]:
			if to in component:
				edge += 1
	
	return sorted(list(component)), edge / len(component) 

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)

for _ in range(M):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)

result, density = [], 0

for i in range(1, N + 1):
	if not visited[i]:
		temp, tempDensity = bfs(i)
		
		if abs(tempDensity - density) < 1e-8:
			if len(result) > len(temp):
				result = temp
				density = tempDensity
			elif len(result) == len(temp):
				if temp[0] < result[0]:
					result = temp
					density = tempDensity
		elif tempDensity > density:
			result = temp
			density = tempDensity

print(*result)

Day18 중첩 점 - 구름LEVEL (goorm.io)

내 풀이 과정

중첩점은 아주 쉽게 풀어냈던것 같다

탐색해야 할 범위는 사전으로 작성했고 y x 축이 교차하는 지점만 중첩점으로 판단할 수 있도록 y축, x축 라인 유무를 따로 저장할 수 있도록 리스트를 선언하여 교점을 곱해 답을 찾아냈다.

 

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean

N, M = map(int, input().split())

nemo = [[[0,0] for _ in range(N)] for _ in range(N)]
direction = {'U':[0,-1], 'D':[0,1], 'L':[-1,0],'R':[1,0]}
result=0
for _ in range(M):
	sy, sx, d = input().split()
	sy = int(sy)-1
	sx = int(sx)-1
	dx, dy = direction[d]
	
	mul = 0
	while True:
		cy = sy + dy*mul
		cx = sx + dx*mul
		if cy >= N or cx >= N or cy < 0 or cx < 0:
			break
		else:
			if d == 'D' or d == 'U':	
				nemo[cy][cx][1] +=1
			else:
				nemo[cy][cx][0] +=1
		mul+=1

for i in range(N):
	for j in range(N):
		result += nemo[i][j][0] * nemo[i][j][1]

print(result)

정해 코드

하지만 역시나 정해코드는 나보다 훨씬 간결한 코드를 가지고 있었다.

 

N, M = map(int, input().split())
arr = [[[0, 0] for _ in range(N)] for _ in range(N)]

for _ in range(M):
	y, x, d = input().split()
	y = int(y) - 1
	x = int(x) - 1

	if d == "R":
		for j in range(x, N):
			arr[y][j][1] += 1
	elif d == "L":
		for j in range(x + 1):
			arr[y][j][1] += 1
	elif d == "U":
		for i in range(y + 1):
			arr[i][x][0] += 1
	elif d == "D":
		for i in range(y, N):
			arr[i][x][0] += 1

result = 0

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