크루스칼 알고리즘을 사용해서 쉽게 풀 수 있었다. 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])
단순히 그래프의 순환을 찾아서 출력하는 문제. 순환을 찾기 -> 해당 순환의 첫노드와 마지막 노드까지를 answer 배열에 넣기 -> 다음 순환 찾기의 반복으로 풀 수 있었다.
(1) 순환 찾기
for (int i = 1; i <= N; i++) {
if (!visited[i] && !visited[nums[i]]) checkCycle(i); //현재 노드와 연결된 노드 둘 다 아직 방문한 적이 없는 노드라면 checkCycle
visited[i] = true; //visited 갱신
}
현재 노드와 연결된 노드를 둘 다 보는 이유는 현재 노드는 당연히 방문한 적이 없어야 하고, 연결된 노드가 이미 방문된 노드라면 앞에서 순환 검사를 이미 끝마쳤다는 소리이기 때문
void checkCycle(int node) {
visited[node] = true; //visited 갱신
int next = nums[node];
//만일 순환이 발생한다면
if (visited[next]) {
addAnswer(next, node);//순환의 처음과 끝을 가지고 addAnswer수행
return;
}
checkCycle(next); //순환이 발생하지 않으면 연결된 다음 노드로 이동
}
(2) answer배열에 추가하기
void addAnswer(int start, int goal) {
int current = start;
answer.push_back(current);
// 그래프를 타고 다음 노드로 넘어가며 goal과 같은 노드에 다다르기 전까지 answer 배열에 추가
while (current != goal) {
current = nums[current];
answer.push_back(current);
}
}
3. 전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int nums[101];
bool visited[101];
vector<int> answer;
void addAnswer(int start, int goal) {
int current = start;
answer.push_back(current);
while (current != goal) {
current = nums[current];
answer.push_back(current);
}
}
void checkCycle(int node) {
visited[node] = true;
int next = nums[node];
if (visited[next]) {
addAnswer(next, node);
return;
}
checkCycle(next);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) cin >> nums[i];
for (int i = 1; i <= N; i++) {
if (!visited[i] && !visited[nums[i]]) checkCycle(i);
visited[i] = true;
}
cout << answer.size()<<'\n';
sort(answer.begin(), answer.end());
for (auto& ele : answer) cout << ele << '\n';
}
빠져나올 수 없는 시간 초과의 늪... + 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])))
