트리가 주어지고, 1번 노드가 루트라고 할 때 각 노드의 부모 노드 번호를 구하는 문제이다.
root 노드인 1번부터 시작해 BFS or DFS를 사용해서 트리를 탐색하고, 각 노드의 부모 노드를 갱신해주면 된다.
소스 코드
import sys
import collections
N = int(sys.stdin.readline())
graph = collections.defaultdict(list)
parent = collections.defaultdict(int)
Q = collections.deque([])
discovered = [False for _ in range(N+1)]
for _ in range(N-1):
A, B = map(int, sys.stdin.readline().split())
graph[A].append(B)
graph[B].append(A)
Q.append(1)
while Q:
cur = Q.popleft()
for i in graph[cur]:
if discovered[i]:
continue
parent[i] = cur
discovered[i] = True
Q.append(i)
for i in range(2, N+1):
print(parent[i])
원형으로 앉아있는 사람들 N명끼리 1 ~ N이 써져 있는 카드를 뽑고 버린 후, 뽑은 숫자만큼 공을 오른쪽으로 패스해서, 모든 사람들이 1번씩 공을 패스받았을 때 공이 이동한 순서를 출력하는 문제이다.
N번 카드를 뽑는 것은 공을 맨 처음 가지고 있는 1번 사람만이 가능하다. 1번 사람을 제외한 모든 사람은 공을 받으려면 일단 타인에게 패스를 받아야 하는데, N번 카드를 뽑으면 공이 한 바퀴 돌아서 자신에게 돌아오기 때문에 패스를 2번 받게 되어버리기 때문이다.
첫 번째 사람을 N번 카드를 뽑는다고 고정시키면, 나머지 카드는 1 ~ N-1이 남게 된다. 그런데 N이 홀수라면, 남은 카드의 합 (N(N-1) / 2) - N이 N의 배수가 되어 첫 번째 사람이 패스를 최소 1번 추가로 받게 된다. 따라서 N이 1을 제외한 홀수인 경우 모든 사람이 한 번씩만 패스를 받을 수는 없다.
N이 짝수인 경우 N, 1, N-2, 3, N-4, 5, N-6, 7 ... 순으로 카드를 뽑아서 패스할 경우 모든 사람이 한 번씩만 패스를 받을 수 있다. 다른 경우도 더 존재할 것 같지만 저런 케이스를 출력하여 문제를 해결하였다.
소스 코드
import sys
N = int(sys.stdin.readline())
if N == 1:
print(1)
exit(0)
if N % 2 == 1:
print(-1)
exit(0)
answer = []
left = N
right = 1
while(True):
answer.append(str(left))
left -= 2
if len(answer) == N:
break
answer.append(str(right))
right += 2
if len(answer) == N:
break
print(' '.join(answer))
직사각형 NxM 텃밭에 즈티가 가로 한 줄, 혹은 세로 한 줄을 지정해 임의의 연속한 K개의 딸기를 심고, 레오가 가로 한 줄, 혹은 세로 한 줄을 지정해 임의의 연속한 토마토 K개를 심는다. 씨앗의 종류에 상관 없이 씨앗이 심어진 영역의 좌표가 주어질 때, 딸기와 토마토가 모두 자라는 텃밭 영역의 칸 수와 해당 칸수를 출력하는 문제이다.
텃밭에서 씨앗이 심겨진 칸의 개수를 seed라 하자. 그렇다면 2K - seed의 값이 딸기와 토마토가 같이 심어진 칸의 수임을 쉽게 유추할 수 있을 것이다. 이 경우에 아래의 3가지 경우를 고려할 수 있다.
1. 2K == seed
이 경우에는 딸기와 토마토가 어떠한 영역에도 같이 심어지지 않았을 것이다. 같이 심어졌으려면 seed가 2K보다는 적어야 한다. 그냥 0을 출력해주면 된다.
1.5. K == 1
2K == seed가 아니면서 K == 1이면 board를 살펴보다가 1이 나오는 순간 그 지점의 좌표를 출력해주면 된다.
2. 2K - 1 == seed
딸기와 토마토가 같이 심겨진 영역이 한 칸만 존재하는 경우이다. 딸기를 심는 영역과 토마토를 심는 영역이 가로, 세로 직선이 교차하면서 생기는 경우가 있는데, 그 경우에는 같이 심기는 공간이 1칸만 존재할 수 있고, 2K - 1 == seed일때 이러한 상황이 발생할 수 있다. 따라서 2K - 1일때 모든 칸에 대해 현재 칸에 씨앗이 심겨져 있고, 가로로 왼쪽 혹은 오른쪽에 씨앗이 존재하면서 세로로 위쪽 혹은 아래쪽에 씨앗이 존재하는 경우에는 교차하면서 같이 심기는 경우로 판단하여 한 칸의 좌표만 출력해주었다.
3. 2K - 1 >= seed
seed가 2K - 1보다 작거나, 2K - 1 == seed 인데 가로 세로 직선이 교차하면서 같이 심기는게 아닌 경우가 있다. 이 때는 딸기 영역과 토마토 영역이 가로 직선 - 가로 직선이 겹치거나, 세로 직선 - 세로 직선이 겹쳐서 같이 심기는 영역이 발생하는 경우이다. board를 확인하면서 가로-가로, 세로-세로 겹침중 어느 것인지 판단 후, 겹친 갯수와 겹친 부분을 출력해주면 된다. 겹친 부분은 겹치기 시작한 부분 + seed - K부터 1씩 늘려가면서 2K-S개를 세주면 구할 수 있다. 왜 이렇게 되는지 모르겠다면 코드를 참고하고 그림을 그려가며 생각해보자.
소스 코드
import sys
def one_check(b, N, M):
dx = [1, -1]
dy = [1, -1]
for y in range(N):
for x in range(M):
if board[y][x] == 0:
continue
check_x = False
check_y = False
for i in range(2):
nx = x + dx[i]
if 0 <= nx < M and board[y][nx] == 1:
check_x = True
ny = y + dy[i]
if 0 <= ny < N and board[ny][x] == 1:
check_y = True
if check_x and check_y:
return f'{y+1} {x+1}'
return None
N, M, K = map(int, sys.stdin.readline().split())
board = []
for _ in range(N):
board.append(list(map(int, sys.stdin.readline().split())))
seed = 0
for i in board:
for j in i:
if j == 1:
seed += 1
if 2*K == seed:
print(0)
exit(0)
print(2*K - seed)
if K == 1:
for y in range(N):
for x in range(M):
if board[y][x] == 1:
print(f'{y+1} {x+1}')
exit(0)
if 2*K - 1 == seed:
check = one_check(board, N, M)
if check is not None:
print(check)
exit(0)
start_x, start_y = 2001, 2001
end_x, end_y = -1, -1
for y in range(N):
for x in range(M):
if board[y][x] == 1:
start_x = min(x, start_x)
start_y = min(y, start_y)
end_x = max(x, end_x)
end_y = max(y, end_y)
if start_x == end_x:
for i in range(2*K - seed):
print(f'{start_y + seed - K + i + 1} {start_x + 1}')
exit(0)
if start_y == end_y:
for i in range(2*K - seed):
print(f'{start_y + 1} {start_x + seed - K + i + 1}')
서로 다른 정수 N개의 모든 쌍의 차를 구할 때, 서로 다른 차의 개수의 최대값과 최소값을 구하는 문제이다.
모든 쌍의 개수는 NC2 = N(N-1) / 2 이고 NC2개의 모든 쌍의 차가 전부 다른 값을 가질 때 서로 다른 차의 개수가 최대가 될 것 같다. 이런 경우가 존재하는지 생각해보자.
특정 수의 배수로도 만들어보고, 소수들로만도 한번 해보고... 여러 숫자를 넣어가면서 규칙을 찾다보면 1, 2, 4, 8... 과 같은 등비수열에서 모든 쌍의 차가 다른 값을 가짐을 파악할 수 있다. 마침 문제에서 N도 최대 30으로 주었고, 2^30이 int의 최대값을 넘어가지 않으므로 2배씩 커지는 등비수열을 출력해주면 실례가 된다. 서로 다른 차의 개수의 최대값은 N(N-1) / 2, 실례는 공비를 2로 갖는 등비수열을 출력해주면 된다.
서로 다른 차의 개수가 최소가 되는 경우는 언제인가? 여러가지 수를 넣어보면서 규칙을 찾다 보면 1, 2, 3, 4... 나 2, 4, 6, 8... 과 같은 등차수열에서 서로 다른 차의 개수가 N-1개로 가장 적어보인다. 다른 숫자 쌍을 넣어봐도 N-1개 보다 줄어드는 경우는 나타나지 않는다. 따라서 서로 다른 차의 개수의 최소값은 N-1, 실례는 임의의 공차를 갖는 등차수열을 출력하면 문제가 풀릴 것 같다.
실제로 코드를 작성하니 문제가 해결되었다.
소스 코드
import sys
N = int(sys.stdin.readline())
print(N*(N-1) // 2)
number = 1
for _ in range(N):
print(number, end=' ')
number *= 2
print()
print(N-1)
number = 1
for _ in range(N):
print(number, end=' ')
number += 1
친분 관계 사이를 기반으로 튜터-튜티 지정이 가능하며, 교육 자료는 튜터 -> 튜티 방향으로 전달할 수 있다. 교육생간의 친분 관계가 포레스트인 그래프로 주어질 때 모든 교육생에게 자료가 전달되기 위해 찬솔이가 전해줘야 하는 인원수의 최소가 될 때의 튜터-튜티 관계를 정하는 경우의 수를 구하는 문제이다.
각 연결요소에 속해있는 정점의 개수를 정답 변수에 곱하는 방법으로 답을 구할 수 있다. 1 - 2 - 3, 4 - 5 - 6 - 7 - 8 이렇게 연결되어 있을 때의 경우는 3x5 = 15개의 경우의 수가 나올 것이다.
소스 코드
import sys
import collections
def bfs(x, visit, graph):
q = collections.deque([x])
visit[x] = True
number = 1
while q:
cur = q.popleft()
for nxt in graph[cur]:
if visit[nxt]:
continue
q.append(nxt)
visit[nxt] = True
number += 1
return number
graph = collections.defaultdict(list)
N, M = map(int, sys.stdin.readline().split())
visit = [False for _ in range(N+1)]
answer = 1
mod = 1000000007
for _ in range(M):
u, v = map(int, sys.stdin.readline().split())
graph[u].append(v)
graph[v].append(u)
for v in range(1, N+1):
if not visit[v]:
answer *= bfs(v, visit, graph)
answer %= mod
print(answer)
상하좌우 배추에 배추흰지렁이가 옮겨서 해충으로 부터 보호할 수 있을 때, 격자 모양의 밭의 모든 배추를 보호하려면 배추흰지렁이가 몇 마리 필요한지 구하는 문제이다.
연결 요소의 개수를 구하라는 문제와 같다. flood-fill을 bfs로 구현하고 미방문 배추를 bfs로 방문해주면서 연결 요소의 개수를 세주면 된다.
소스 코드
#include <iostream>
#include <queue>
using namespace std;
bool board[51][51];
bool visit[51][51];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int M, N, K;
void bfs(int y, int x) {
queue<pair<int, int>> Q;
visit[y][x] = true;
Q.push(make_pair(y, x));
while(!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int i = 0; i < 4; i++) {
int ny = cur.first + dy[i];
int nx = cur.second + dx[i];
if (0 <= ny && ny < N && 0 <= nx && nx < M) {
if (!board[ny][nx]) continue;
if (visit[ny][nx]) continue;
visit[ny][nx] = true;
Q.push(make_pair(ny, nx));
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
cin >> M >> N >> K;
int Y, X;
int answer = 0;
for (int i = 0; i < K; i++) {
cin >> X >> Y;
board[Y][X] = true;
}
for (int i = 0 ; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] && !visit[i][j]) {
answer++;
bfs(i, j);
}
}
}
cout << answer << '\n';
for (int i = 0; i < 51; i++) {
for (int j = 0; j < 51; j++) {
board[i][j] = false;
visit[i][j] = false;
}
}
}
return 0;
}
현재 N에 있고, 동생이 K에 있을 때, 하루마다 현재 점에서 +1, -1, *2로 이동이 가능한데, 동생을 찾는 가장 빠른 시간을 구하는 문제이다.
BFS로 +1, -1, *2 이동해보면서 원점으로 부터의 거리를 계산하고, K일때 원점에서의 거리를 출력해주면 된다. 동생이 10만까지만 위치 가능하긴 해도, 수빈이는 10만을 넘어선 점에 위치가 가능하긴 한데 이 문제에서는 10만을 넘어가면 무조건 원점과 10만까지의 거리보다 더 많은 거리를 이동해야 하므로 고려해주지 않아도 된다.
소스 코드
#include <iostream>
#include <queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int d[100001];
for (int &i : d) {
i = -1;
}
queue<int> Q;
int N, K;
cin >> N >> K;
d[N] = 0;
Q.push(N);
while(!Q.empty()) {
int cur = Q.front(); Q.pop();
if (cur == K) {
cout << d[K];
return 0;
}
for (int next : {cur-1, cur+1, 2*cur}) {
if (next < 0 || next > 100000) continue;
if (d[next] != -1) continue;
d[next] = d[cur] + 1;
Q.push(next);
}
}
return 0;
}
