[구름톤 챌린지] Day11 ~ Day13

💡 학습 일기

탐색 주가 시작됐다

BFS, DFS 머리가 아프지만 프로그래밍을 처음 공부했을 때부터 접했던 부분이라 중요한 것은 알겠다. :(

리스트를 순회하고 답을 찾는 완전 탐색은 OK

Day11 문제는 지난 주 통증 문제에서 업그레이드 됐다. 가능한 답을 모두 찾고 그 중에서 최소의 답을 찾았다.
그래도 간단한 계산 문제여서 어렵지 않았다.

너비우선탐색과 깊이우선탐색 - Day12, Day13

스택과 큐, 덱은 탐색의 재료일 뿐...
다음 노드로 넘어가서 반복해서 탐색해야 하기 때문에 재귀함수나 while, for문을 잘 활용해야 한다.

💡 코드 공부

Day 11: 통증 (2)

Bp가 큰 수이므로, 먼저 나눈 후, Bp만큼 남기면서 Ap의 갯수를 구한 뒤 가장 최솟값을 찾는다.

n = int(input())
ap, bp = map(int, input().split())

items = []
for i in range(n//bp+1):
	if ((n%bp)+(bp*i))%ap == 0:
		items.append(n//bp - i + ((n%bp)+(bp*i))//ap)

if not items:
	print(-1)
else:
	print(min(items))

if items == []:를 if not items로 쓸 수도 있다는 것을 알게됐다.

Day 12: 발전기

DFS (깊이 우선 탐색) : 방문하는 방향으로 최대한 깊게 탐색 후, 처음으로 돌아와서 다음 방향으로 탐색
BFS (너비 우선 탐색) : 현재 위치를 기준으로 방문이 가능한 모든 위치를 탐색 후, 이전 단계에서 구한 '위치들'을 기준으로 다시 방문이 가능한 위치 탐색

• 재귀 DFS의 경우, 초기에 지정한 순서로 바로 이동하여 탐색
  상하좌우 1이 없는 경우 이전 단계로 돌아올 수 있는 이유: for문이 아직 끝나지 않았기 때문에. 재귀를 하면 반복적으로 for문이 돌아간다.
  이 경우 재귀 깊이 제한 1000번으로 인해 런타임 에러가 발생할 수 있다.
• 비재귀 DFS의 경우, 스택을 활용해서, 최근에 스택에 추가된 위치부터 탐색한다.
• BFS의 경우, 큐를 활용해서, 먼저 큐에 추가된 위치부터 탐색한다. 즉, 시작 위치부터 가까운 모든 위치를 탐색 후, 다음 거리의 위치를 탐색한다.

스택 또는 큐의 오른쪽에 값을 추가하는건 동일하지만, 값을 왼쪽에서 꺼내는지, 오른쪽에서 꺼내는지에 따라 탐색을 진행하는 방식이 달라진다

Day 13: 발전기 (2)

DFS/BFS + 리스트 완전탐색
정해코드는 M의 가능한 범위 안(range(31))에서 단지의 갯수를 탐색했지만,
나는 건물유형과 그 갯수를 튜플로 묶어 return 후 K 이상일 때 리스트에 추가했다.
그 다음 그 리스트에서 건물 유형에 따른 단지 갯수를 튜플로 묶어 다시 리스트화 한 후, (1) 단지 갯수 (2) 건물 유형을 내림차순으로 이중 정렬하여 첫번째 요소의 단지 갯수를 출력하였다.

from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

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


def bfs(i, j):
	global M, K, dy, dx, arr
	
	q = deque([(i, j)])
	mk = 0
	
	while q:
		y, x = q.popleft()
		
		if arr[y][x] == 0:
			continue
			
		M = arr[y][x]
		arr[y][x] = 0
		mk += 1
		
		for k in range(4):
			ny, nx = y + dy[k], x + dx[k]
			
			if ny in (-1, N) or nx in (-1, N) or arr[ny][nx] == 0:
				continue
				
			elif arr[ny][nx] == M:
				q.append((ny, nx))
	
	return (M, mk)
	
	
mlist = []
for i in range(N):
	for j in range(N):
		building, number = bfs(i, j)
		if number >= K:
			mlist.append(building)

mset = set()
for l in mlist:
	mset.add((l, mlist.count(l)))

# mset = {(3, 2), (2, 2), (1, 1), (4, 1)}
mset = sorted(sorted(mset, key=lambda x: x[0], reverse=True), key=lambda x:x[1], reverse=True)
print(mset[0][0])