크루스칼 알고리즘을 사용해서 쉽게 풀 수 있었다. Union-Find 코드를 중간에 이상하게 틀려서 헤메긴 했지만... 조금 더 완벽히 숙지해야겠다.
간단한 코드이므로 블락 단위의 설명은 생략하겠음.
3. 전체 코드
import sys
#Union-Find
def find(x):
if x == root[x]:
return x
else: return find(root[x])
def union(a, b):
root_a, root_b = find(a), find(b)
root[root_b] = root_a
N = int(input())
stars = [list(map(float, sys.stdin.readline().split())) for _ in range(N)]
root = [_ for _ in range(N)]
costs = {} #{(별1, 별2): distance} 형태의 딕셔너리(딱히 딕셔너리 아니어도 됨)
#모든 별들 간에 간선이 있다고 가정 => 비용 계산하여 저장
for i in range(N):
for j in range(i+1, N):
a = stars[i]
b = stars[j]
dist = round(((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5, 2)
costs[(i, j)] = dist
#크루스칼 알고리즘을 위해 distance의 오름차순으로 정렬
costs = sorted(costs.items(), key = lambda x: x[1])
#크루스칼 알고리즘
answer = 0
while costs:
current = costs.pop(0)
a, b = current[0]
cost = current[1]
#같은 그룹에 있는 것이 아니라면
if find(a) != find(b):
answer += cost
union(a, b)
print(answer)
전형적인 DP문제. 처음에는 근우의 입장에서만 생각하고 코드를 짠 후 당당하게 제출했는데 역시 당당하게 틀렸다. 해당 문제는 다음과 같이 근우의 차례일 때와 명우의 순서일 때를 나누어서 생각해야 한다.
(1) 근우의 순서일 때
- 왼쪽 카드를 선택하고 나머지 카드들에서 얻는 점수, 오른쪽 카드를 선택하고 나머지 카드들에서 얻는 점수 중 최댓값
(2) 명우의 순서일 때
- 왼쪽 카드 제외한 나머지 카드들에서 얻는 점수, 오른쪽 카드 제외한 나머지 카드들에서 얻는 점수 중 최솟값
- 근우가 점수를 작게 가져가게끔 만들어야하도록 최솟값일 때의 경우를 선택
간단한 코드이므로 코드 블락 단위의 설명은 주석으로 대체하겠음.
3. 전체 코드
def pickCard(turn, i, j):
if i > j: return 0
if dp[i][j]: return dp[i][j] #이미 계산된 적이 있으면 해당 값 리턴
#근우 차례
if turn:
# i카드 + (i+1~j)범위 카드의 명우 순서 or j카드 + (i~j-1)범위 카드의 명우 순서 중 최대 스코어
score = max(pickCard(False, i+1, j) + cards[i], pickCard(False, i, j-1) + cards[j])
dp[i][j] = score
return score
#명우 차례
elif not turn:
# (i+1~j)범위 카드의 근우 순서 or (i~j-1)범위 카드의 근우 순서 중 최소 스코어
# 각각 명우가 i, j 카드를 가져갔다고 가정하지만, 근우 입장의 점수를 계산하는 거기 때문에 카드 점수를 더해주지 않음
score = min(pickCard(True, i+1, j), pickCard(True, i, j-1))
dp[i][j] = score
return score
import sys
T = int(input()) #테스트케이스
for _ in range(T):
N = int(input()) #카드 개수
cards = list(map(int, sys.stdin.readline().split()))
dp = [[0 for _ in range(N)] for _ in range(N)] #DP 배열 초기화
pickCard(True, 0, N-1) #카드가 (0~N-1)범위만큼 있고, 근우 순서일 때 얻는 점수 계산
print(dp[0][N-1])
빠져나올 수 없는 시간 초과의 늪... + 10으로 나눈 나머지를 출력하라는 데 바보 같이 그냥 출력하고 있었음.
문제를 꼼꼼히 읽자...ㅎㅎ 처음에는 무작정 BFS로 짰다가 계속 시간초과가 나길래 (구글의 도움을 빌려서) 코드를 수정했다. 찾아보기로는 플러드 필이라는 알고리즘 구현을 요구하는 문제라고 한다. 처음 듣는 알고리즘이라 해당 알고리즘에 대해서는 나중에 별도로 정리해봐야겠다.
1. 인접해 있는 0을 묶어서 그룹 인덱스를 붙임
2. 해당 그룹에 0이 총 몇 개가 포함되어있는지를 저장하는 딕셔너리 생성
3. 보드를 돌 때마다 1을 만나면 상하좌우 그룹의 0 개수를 전부 더해서 출력(2번의 딕셔너리 이용)
위의 설명은 직관적으로 와닿지 않을 수도 있으니 아래 코드의 주석으로 자세히 설명하겠다.
(1) 초기화 및 설정
N, M = map(int, input().split())
board = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
zeros = [[0 for _ in range(M)] for _ in range(N)]
board : 전체 맵
visited : BFS를 통해 이미 방문했는지, 아닌지 확인
zeros : 인접한 0끼리 같은 그룹으로 묶어서 표시
(2) BFS - 그룹표시
group = 1
info = {}
for i in range(N):
for j in range(M):
if not board[i][j] and not visited[i][j]: #0인 칸이고 아직 방문하지 않은 노드이면
cnt = BFS(i, j) #BFS수행해서 인접한 0의 개수 리턴
info[group] = cnt #{index: cnt} 꼴로 삽입
group += 1 #그룹 인덱스 갱신
group : 그룹 인덱스
info : {index: cnt} 형태의 딕셔너리. 각 그룹에 포함된 0의 개수 저장
아직 방문하지 않은 0인 칸마다 BFS수행해서 그룹 인덱스 표시해주고, 그룹별 0의 갯수 딕셔너리에 추가
def BFS(x, y):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
q.append([x, y])
visited[x][y] = 1
cnt = 1
while q:
current_x, current_y = q.pop()
zeros[current_x][current_y] = group #그룹 인덱스 표시
for dx, dy in dir:
next_x, next_y = current_x + dx, current_y + dy
if next_x < 0 or next_y < 0 or next_x >= N or next_y >= M: continue
if visited[next_x][next_y]: continue
if not board[next_x][next_y]:
q.append([next_x, next_y])
visited[next_x][next_y] = 1
cnt += 1
return cnt
(3) 상하좌우 가능한 Move 개수 세기
answer = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
for j in range(M):
if board[i][j]:
answer[i][j] = countMoves(i, j)
def countMoves(x, y):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상하좌우 확인
candidates = set() #중복 제거 위해 set 사용
for dx, dy in dir:
next_x, next_y = x + dx, y + dy
if next_x < 0 or next_y < 0 or next_x >= N or next_y >= M: continue
if not zeros[next_x][next_y]: continue #그룹 인덱스가 0 = 보드값이 1
candidates.add(zeros[next_x][next_y]) #그룹 인덱스추가
cnt = 1
for c in candidates: #그룹들 전부 돌면서 cnt 더해주기
cnt += info[c]
cnt = cnt % 10 #10으로 나눈 나머지!
return cnt
3. 전체 코드
import sys
from collections import deque
def BFS(x, y):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
q.append([x, y])
visited[x][y] = 1
cnt = 1
while q:
current_x, current_y = q.pop()
zeros[current_x][current_y] = group
for dx, dy in dir:
next_x, next_y = current_x + dx, current_y + dy
if next_x < 0 or next_y < 0 or next_x >= N or next_y >= M: continue
if visited[next_x][next_y]: continue
if not board[next_x][next_y]:
q.append([next_x, next_y])
visited[next_x][next_y] = 1
cnt += 1
return cnt
def countMoves(x, y):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
candidates = set()
for dx, dy in dir:
next_x, next_y = x + dx, y + dy
if next_x < 0 or next_y < 0 or next_x >= N or next_y >= M: continue
if not zeros[next_x][next_y]: continue
candidates.add(zeros[next_x][next_y])
cnt = 1
for c in candidates:
cnt += info[c]
cnt = cnt % 10
return cnt
N, M = map(int, input().split())
board = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
zeros = [[0 for _ in range(M)] for _ in range(N)]
group = 1
info = {}
for i in range(N):
for j in range(M):
if not board[i][j] and not visited[i][j]:
cnt = BFS(i, j)
info[group] = cnt
group += 1
answer = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
for j in range(M):
if board[i][j]:
answer[i][j] = countMoves(i, j)
for i in range(N):
print(''.join(map(str, answer[i])))
처음에는 대충 원하는 대로 구현했다가 참패... 20%빼고 런타임에러를 맞는 기적을 경험했다. 유력한 가설은 아마 시간초과나 메모리 초과가 아닐까...
그 다음 어떻게 짜야할 지 감이 잡히지 않아서 결국 검색의 도움을 빌렸다. 다른 분들의 풀이를 참고해서 아래와 같이 해결하였다.
1. 같은 그룹으로 묶일 수 있는 칸끼리 묶기 (BFS)
2. 각 그룹간의 이동 거리 구하기
3. 최소 이동 거리 구하기 (MST)
(1) 초기화 및 설정
N = len(land)
check = [[0 for _ in range(N)] for _ in range(N)] # 각 칸의 그룹
(2) BFS
group = 1
for i in range(N):
for j in range(N):
if not check[i][j]: # 아직 그룹이 정해지지 않은 칸이라면
BFS(land, height, check, [i, j], group, N)
group += 1
N*N의 칸을 모두 돌면서 아직 그룹이 정해지지 않은 칸이 있다면 해당 칸을 기점으로 BFS를 수행
def BFS(land, height, check, loc, group, N):
direction = [(0, -1), (0, 1), (1, 0), (-1, 0)]
q = deque()
q.append(loc)
check[loc[0]][loc[1]] = group
while q:
x, y = q.popleft()
for dx, dy in direction:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= N or ny < 0 or ny >= N or check[nx][ny]: continue
if abs(land[nx][ny] - land[x][y]) <= height: # 이동하려는 칸과의 높이 차가 작다면
q.append([nx, ny]) # 큐에 넣기
check[nx][ny] = group # 그룹 표시
(3) 각 그룹간의 이동거리 계산
def find_ladder(check, land, N):
direction = [(0, -1), (0, 1), (1, 0), (-1, 0)]
ladders = defaultdict(lambda: math.inf) # 최대값으로 초기화
for i in range(N):
for j in range(N):
current = check[i][j]
for dx, dy in direction:
nx, ny = i + dx, j + dy
if nx < 0 or nx >= N or ny < 0 or ny >= N or check[nx][ny] == current: continue # 같은 그룹에 속해 있다면 건너뜀
dist = abs(land[i][j] - land[nx][ny])
ladders[(current, check[nx][ny])] = min(dist, ladders[(current, check[nx][ny])]) # 최소거리로 갱신
return ladders
ladders : {(x, y): value} 형태로 되어있는 딕셔너리. x그룹에서 y그룹으로 이동할 때 필요한 사다리의 비용을 가지고 있음
(4) MST
def kruskal(ladders, group):
sum = 0
roots = {_:_ for _ in range(1, group)} # 정점들 root 표시
for (x, y), value in ladders:
if find_root(x, roots) != find_root(y, roots): # root가 같지 않을 경우
union_find(x, y, roots) # root 연결
sum += value # 값 갱신
if len(roots.items()) == 1: return sum # 노드들이 전부 연결된 경우 리턴
return sum
크루스칼 알고리즘으로 MST 구현
Union-find를 적용해서 각 노드의 루트로 올라가 루트가 같지 않을 경우에 값을 갱신해주었다!
3. 전체 코드
from collections import deque, defaultdict
import math
def find_root(x, root):
if x == root[x]: return x
else:
r = find_root(root[x], root)
root[x] = r
return r
def union_find(x, y, root):
x_root = find_root(x, root)
y_root = find_root(y, root)
root[y_root] = x_root
def BFS(land, height, check, loc, group, N):
direction = [(0, -1), (0, 1), (1, 0), (-1, 0)]
q = deque()
q.append(loc)
check[loc[0]][loc[1]] = group
while q:
x, y = q.popleft()
for dx, dy in direction:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= N or ny < 0 or ny >= N or check[nx][ny]: continue
if abs(land[nx][ny] - land[x][y]) <= height:
q.append([nx, ny])
check[nx][ny] = group
def find_ladder(check, land, N):
direction = [(0, -1), (0, 1), (1, 0), (-1, 0)]
ladders = defaultdict(lambda: math.inf)
for i in range(N):
for j in range(N):
current = check[i][j]
for dx, dy in direction:
nx, ny = i + dx, j + dy
if nx < 0 or nx >= N or ny < 0 or ny >= N or check[nx][ny] == current: continue
dist = abs(land[i][j] - land[nx][ny])
ladders[(current, check[nx][ny])] = min(dist, ladders[(current, check[nx][ny])])
return ladders
def kruskal(ladders, group):
sum = 0
roots = {_:_ for _ in range(1, group)}
for (x, y), value in ladders:
if find_root(x, roots) != find_root(y, roots):
union_find(x, y, roots)
sum += value
if len(roots.items()) == 1: return sum
return sum
def solution(land, height):
answer = 0
N = len(land)
check = [[0 for _ in range(N)] for _ in range(N)]
group = 1
for i in range(N):
for j in range(N):
if not check[i][j]:
BFS(land, height, check, [i, j], group, N)
group += 1
ladders = find_ladder(check, land, N)
ladders = sorted(ladders.items(),key=lambda x:x[1])
answer = kruskal(ladders, group)
return answer
