구름톤 챌린지 Day13, Day15[탐색과 DP]

[문제 13]

n, K = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

result = 0

def dfs(x, y):
    stack = [[x,y]]
    cnt = 0
    M = graph[x][y]
    while stack:
        x, y = stack.pop()
        if graph[x][y] != M:
            continue
        graph[x][y] = 0
        cnt += 1
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n :
                if graph[nx][ny] == M:
                    stack.append([nx, ny])
    return cnt

count = [0] * 31
for i in range(n):
    for j in range(n):
        if graph[i][j]:
            M = graph[i][j]
            if dfs(i, j) >= K:
                count[M] += 1

result, temp = 0, 0

for i in range(31):
    if temp <= count[i]:
        temp = count[i]
        result = i
print(result)

문제 12와 거의 유사한 문제였다. 하지만 단지가 성립되는 조건과 건물 유형이 동일한지에 대한 조건이 추가되었다. 
먼저, 건물 유형이 동일하면서, 단지로 묶이는 즉 dfs로 그룹을 묶었을 때 나오는 한묶음에 해당하는 집의 개수가 단지가 성립되는 조건인지 확인해서 가장 많은 단지가 있는 건물 유형 번호를 구하는 순서를 생각했다. 

dfs로 묶음을 구할 때 동일한 건물 유형일때만 계속 진행하며 노드를 방문했을 때 cnt += 1을 통해 한 묶음에 해단하는 집의 개수를 계산한다. 그 값이 단지에 대한 묶음이면 count를 늘려주고 count를 통해 가장 많은 단지가 있는 유형 번호를 산출할 수 있다. 

 

[문제 15]

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

arr.sort(key=lambda x : x[1] // x[0])
result = 0
while K and arr:
	p, c = arr.pop()
	if K >= p:
		result += c
		K -= p
	else:
		result += c // p * K
		K = 0

print(result)

1. 모든 과일을 조각내어 배열에 집어넣는 경우

# 조각을 담을 배열을 선언하고 데이터를 담아줄게요.
piece = []
for P, C in arr:
	for _ in range(P):
		piece.append(C // P)
        
# 큰 조각부터 사기 위해 정렬해줍니다.
piece.sort()

1조각의 포만감을 조각난 과일의 개수만큼 배열에 추가해줘서 현재 몇조각의 과일이 존재하는지, 정렬을 통해 1조각당 포만감이 큰 조각부터 사도록 진행했다. 
-> 이렇게하면 몇개 케이스에서 에러가 나오는데, 1조각당 포만감이 10억이라면 해당 배열에 과일조간이 10억개가 들어가야한다. 이는 메모리와 시간에서 문제를 발생시킨다. 

2. 위 한계를 극복하기 위해 1조각 당 포만감의 오름차순으로 정렬하여 
     a. 만약 꺼낸 과일 가격이 현재 K 보다 크거나 같다면 통째로 고려
     b. 아니라면, 조각으로 나누고 가격에 맞춰 구매

3. 2번으로 진행하면 대부분의 케이스를 통과할 수 있다. 
    이 케이스를 고려하는 것이 가장 생각이 안났던 것 같다. --> 모든 과일을 전부 구매했는데 돈이 남은 경우에는 arr이 계        속 비어있는 상태가 되기 때문이다. 따라서 arr 배열에 값이 있는 동안만 반복만이 돌도록 조건을 추가해주면 원하는 결      과를 만날 수 있다.