위 풀이의 Python 버전입니다. 크게 다를건 없고 Python이 코드라인이 훨씬 적습니다.
import sys
from collections import deque
nm = sys.stdin.readline().split(' ')
M = int(nm[0])
N = int(nm[1])
B, W = 0, 0
maps = []
delta = [[-1, 0],[1, 0],[0, -1],[0, 1]]
for n in range(N):
maps.append(list(sys.stdin.readline()))
for n in range(N):
for m in range(M):
maps[n][m] = 0 if maps[n][m] == 'W' else 1
for n in range(N):
for m in range(M):
if maps[n][m] in [0, 1]:
target = maps[n][m]
count = 0
queue = deque()
queue.append([n, m])
maps[n][m] = -1
while len(queue) > 0:
x, y = queue.popleft()
count += 1
for i in range(4):
nx = x + delta[i][0]
ny = y + delta[i][1]
if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == target:
queue.append([nx,ny])
maps[nx][ny] = -1
count *= count
if target == 0:
W += count
else:
B += count
print(f"{W} {B}")
추석연휴가 껴 있기도 했고, 개인적인 일로 지방을 오가느라 시간이 없기도 했고.... 무엇보다 근무도 바빴고... 여러 사정이 있었지만 결국엔 제가 게을렀던 거겠죠.
Java를 하도 안쓰다 보니 (현재 하고 있는 업무에서 90% 이상 Python을 씁니다.) 다 까먹어가고 있는 느낌이라 급하게 쉬운 문제를 하나 풀어봤습니다.
정말 기본적인 bfs 문제라 딱히 설명할건 없네요. visit 체크만 잘해주면 풀리는 문제였습니다. 주의 할 점은 N과 M이 거꾸로 주어진다는 정도입니다. 예제에서 티가 안나는 부분이라(예제 입력에선 N == M입니다.) 첫 제출에서 index 범위가 넘어가는 런타임 에러를 당했네요.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class q1303_BOJ_전쟁전투 {
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int B = 0;
int W = 0;
int[][] map = new int[N][M];
Queue<int[]> queue = new LinkedList<int[]>();
for (int n = 0; n < N; n++) {
char[] line = br.readLine().toCharArray();
for (int m = 0; m < M; m++) {
map[n][m] = (line[m] == 'W') ? 0 : 1;
}
}
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
if (map[n][m] == 0 || map[n][m] == 1) {
int target = map[n][m];
int count = 0;
queue.offer(new int[] { n, m });
map[n][m] = -1;
while (!queue.isEmpty()) {
int[] now = queue.poll();
count += 1;
for (int i = 0; i < 4; i++) {
int nx = now[0] + delta[i][0];
int ny = now[1] + delta[i][1];
if (isIn(nx, ny, N, M) && map[nx][ny] == target) {
queue.offer(new int[] { nx, ny });
map[nx][ny] = -1;
}
}
}
if (target == 0) {
W += (count * count);
} else {
B += (count * count);
}
}
}
}
sb.append(W).append(" ").append(B);
System.out.println(sb);
}
private static boolean isIn(int x, int y, int n, int m) {
return 0 <= x && x < n && 0 <= y && y < m;
}
}
각 섬들을 다리로 연결하는 부분은 같지만, 다리만들기1 문제와 다르게 다리는 직선으로만 가능하며 모든 섬이 연결되도록 완성해야 하고 이때 다리의 길이가 2이상인 최소한의 다리를 활용해야 합니다.
이 문제는 크게 3가지 과정으로 나눌 수 있습니다.
1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기
2. 각각의 섬에서 다른 섬으로 잇는 최단 다리를 모두 만들기
3. 다리를 선택해 모든 섬들이 연결되게 만들기.
1,2번 과정은 다리만들기 1번 문제와 비슷하고 3번 과정은 MST(최소 스패닝 트리)를 구하는 과정으로 만들 수 있습니다.
즉, 각각의 섬들이 노드가 되고 각 섬들에서 다른섬으로 연결되는 최소거리의 다리가 엣지가 되는 식입니다.
MST를 만드는 알고리즘은 여러 종류가 있는데 우선순위 큐와 Union만을 이용해 간단하게 구현할 수 있는 크루스칼(Kruskal) 알고리즘을 사용했습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class q17472__BOJ_다리만들기2 {
static StringTokenizer st;
static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
static int[] parent;
static int N, M;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
for (int m = 0; m < M; m++) {
map[n][m] = Integer.parseInt(st.nextToken()) * -1;
}
}
int island = 1;
Queue<int[]> queue = new LinkedList<>();
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
if (map[n][m] == -1) {
queue.offer(new int[] { n, m });
map[n][m] = island;
while (!queue.isEmpty()) {
int[] now = queue.poll();
int x = now[0];
int y = now[1];
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if (isIn(nX, nY) && map[nX][nY] == -1) {
queue.offer(new int[] { nX, nY });
map[nX][nY] = island;
}
}
}
island++;
}
}
}
int[][] graph = new int[island][island];
for (int is = 1; is <= island; is++) {
boolean[][] visit = new boolean[N][M];
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
if (map[n][m] == is) {
queue.offer(new int[] { n, m, 0, 5 });
visit[n][m] = true;
}
}
}
while (!queue.isEmpty()) {
int[] now = queue.poll();
int x = now[0];
int y = now[1];
int l = now[2];
int dir = now[3];
if (dir == 5) {
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if (isIn(nX, nY) && !visit[nX][nY] && map[nX][nY] == 0) {
queue.offer(new int[] { nX, nY, l + 1, i });
visit[nX][nY] = true;
}
}
}
else {
int nX = x + delta[dir][0];
int nY = y + delta[dir][1];
if (isIn(nX, nY) && !visit[nX][nY]) {
if (map[nX][nY] == 0) {
queue.offer(new int[] { nX, nY, l + 1, dir });
visit[nX][nY] = true;
} else {
if (graph[is][map[nX][nY]] == 0 && 1 < l) {
graph[is][map[nX][nY]] = l;
}
visit[nX][nY] = true;
}
}
}
}
}
int answer = 0;
parent = new int[island];
for (int n = 1; n < island; n++) {
parent[n] = n;
}
PriorityQueue<int[]> pqueue = new PriorityQueue<>((e1, e2) -> {
return e1[0] - e2[0];
});
for (int from = 1; from < island; from++) {
for (int to = 1; to < island; to++) {
if (graph[from][to] != 0) {
pqueue.offer(new int[] { graph[from][to], from, to });
}
}
}
while (!pqueue.isEmpty()) {
int[] now = pqueue.poll();
int l = now[0];
int from = now[1];
int to = now[2];
if (find(from) != find(to)) {
answer += l;
union(from, to);
}
}
boolean flag = false;
int parent = find(1);
for (int n = 1; n < island; n++) {
if (find(n) != parent) {
flag = true;
break;
}
}
if (flag) {
System.out.println(-1);
} else {
System.out.println(answer);
}
}
static boolean isIn(int x, int y) {
if (0 <= x && x < N && 0 <= y && y < M) {
return true;
}
return false;
}
static int find(int i) {
if (i == parent[i])
return i;
return parent[i] = find(parent[i]);
}
static void union(int x, int y) {
x = find(x);
y = find(y);
if (x > y)
parent[x] = y;
else
parent[y] = x;
}
}
시간 단축을 위해서는 모든 경우에 대해 다리를 구하고 다리의 길이를 비교하는 것 보다는 최소값을 다리가 완성될 때 마다 갱신하고, 이미 구해진 최솟값을 넘는 경우에는 Queue를 비워버리고 스킵하는 것이 훨씬 빠릅니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class q2146_BOJ_다리만들기 {
static StringTokenizer st;
static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
static int[][] map;
static int[] parent;
static int N;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
for (int m = 0; m < N; m++) {
map[n][m] = Integer.parseInt(st.nextToken()) * -1;
}
}
int island = 1;
for (int n = 0; n < N; n++) {
for (int m = 0; m < N; m++) {
if (map[n][m] == -1) {
dfs(n, m, island);
island++;
}
}
}
int answer = Integer.MAX_VALUE;
Queue<int[]> queue = new LinkedList<>();
for (int is = 1; is <= island; is++) {
boolean[][] visit = new boolean[N][N];
for (int n = 0; n < N; n++) {
for (int m = 0; m < N; m++) {
if (map[n][m] == is) {
queue.offer(new int[] { n, m });
visit[n][m] = true;
}
}
}
int l = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int s = 0; s < size; s++) {
int[] now = queue.poll();
int x = now[0];
int y = now[1];
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if (isIn(nX, nY) && !visit[nX][nY]) {
if (map[nX][nY] == 0) {
queue.offer(new int[] { nX, nY });
visit[nX][nY] = true;
} else {
answer = Math.min(answer, l);
visit[nX][nY] = true;
}
}
}
}
l++;
if (l > answer) {
queue.clear();
}
}
}
System.out.println(answer);
}
static void dfs(int x, int y, int name) {
map[x][y] = name;
for (int i = 0; i < 4; i++) {
int nX = x + delta[i][0];
int nY = y + delta[i][1];
if (isIn(nX, nY) && map[nX][nY] == -1) {
dfs(nX, nY, name);
}
}
}
static boolean isIn(int x, int y) {
if (0 <= x && x < N && 0 <= y && y < N) {
return true;
}
return false;
}
}
예를 들어 2,8,1과 6,3,5가 입력으로 주어졌다고 가정해봅시다. 이를 각각 오름차순 내림차순으로 정렬하면 1,2,8과 6,5,3이 됩니다. 문제의 정답은 앞에서부터 순서대로 두 집합의 수를 곱한 6 + 10 + 24 = 40이 됩니다. 6,3,5의 배열이 바뀌었지만 1,2,8과 6,5,3의 곱의 위치를 바꾸어 1,8,2와 6,3,5로 생각해도 답은 같습니다. 그냥 적합한 순위의 수를 매번 찾기가 귀찮아 정렬해 놓았다고 생각해 버립시다.
아이디어가 맞는지 생각해 보겠습니다.
A에서 기존의 가장 작은 수를 a 라고 하면 a가 아닌 어떤 수는 a+c로 나타낼 수 있을겁니다. (a와 같을 수 있음, 즉 c≥0)
B에서 가장 큰 수를 b라고 하면 b가 아닌 어떤 수는 b-d로 나타낼 수 있을겁니다. (마찬가지로 d≥0)
아이디어가 틀리다면 다른 순서로 수를 배열했을때 합이 더 작아져야합니다.
다른 순서로 수를 배열한다면 기존의 (a * b) + ((a+c) * (b-d))가 (a * (b-d)) + ((a+c) * b)로 대체될겁니다.
각 식을 계산해 풀어주면 1. ab + ab + cb - ad - cd 와 2. ab - ad + ab + cb가 됩니다.
다른 수를 선택해서 합이 더 작아지는 케이스가 있다면 1번 식보다 2번 식이 더 작아야합니다.
즉 1번식 - 2번식 > 0 이 성립해야하는데, 계산해보면 cd < 0이 되고 c와 d는 각각 0 이상의 정수이기 때문에 성립하지 않습니다. (c와 d가 둘 다 0이라면 같은 크기일 순 있지만, 이때의 선택도 정답 조합의 하나가 됩니다.)
따라서 A에서 가장 작은 a와 B에서 가장 큰 b를 곱하는게 최소값이 되는 조합이고, 이렇게 fix된 a와 b를 제외한 A' B'로 다시 최소합을 구한다고 생각하면 같은 증명으로 A와 B의 크기가 1이 될 때까지 적용이 가능합니다.
둘의 크기가 1이라면 당연히 곱할 수 있는 방법이 하나밖에 없겠죠.
따라서 위와같이 정렬된 A와 역정렬된 B를 순서대로 곱한 합이 최소값입니다.
(제가 수학전공이 아니기 때문에 증명은 틀릴 수 있습니다... )
n = int(input())
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))
A.sort()
B.sort(reverse=True)
answer = 0
for i in range(0,n):
answer += int(A[i]) * int(B[i])
print(answer)
핵심아이디어는 돈이 허락하는 범위 안에서 5000원짜리 메뉴를 먹었을때 얻는 상대적 만족도가 가장 큰 경우를 선택해야 한다는 것입니다.
예를 들어서, 극단적으로 5000원짜리 메뉴의 만족도가 1만이라고 해도 1000원짜리 메뉴의 만족도가 9999라면 상대적 만족도는 1에 불과합니다. 또 역으로 1000원짜리 메뉴가 더 만족스러운 경우도 가능할 수 있습니다.
가장 만족스러운 식사를 하려면 날짜와 만족도에 상관없이 상대적 만족도가 큰 5000원짜리 메뉴부터 골라서 가능한만큼 선택하는것이 해결방법입니다.
따라서 A메뉴와 B메뉴의 만족도의 차이를 기준으로 입력된 데이터를 정렬해주고, 돈이 허락하는 한에서 A메뉴를 선택했습니다. 돈이 가능한지 여부는 (골라야하는 남은 메뉴의 갯수 * 1000) + 4000 보다 현재 자금이 크거나 같으면 가능하다고 조건문을 잡아두었고 메뉴를 하나 고를때 마다 자금에서 5000원씩을 빼 주었습니다.
또, 정렬을 통해서 B메뉴의 만족도가 더 큰 시점이 오면 이후로는 전부 B메뉴를 선택했습니다. B메뉴를 선택하기 시작한 경우는 두가지입니다.
1. 돈이 부족해서 남은 모든 식사는 B메뉴로 골라야 한다. (조건문을 통해 보장됨)
2. 남은 모든 식사들은 B메뉴가 A메뉴보다 맛있다. (정렬을 통해 보장됨)
따라서 이후로는 돈 계산을 하지 않고 B메뉴의 만족도를 계속 더해주었습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long answer = 0;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int money = Integer.parseInt(st.nextToken());
int[][] menu = new int[N][2];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
menu[n][0] = Integer.parseInt(st.nextToken());
menu[n][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(menu, (e1, e2) -> {
return (e2[0] - e2[1]) - (e1[0] - e1[1]);
});
int n = 0;
while (money - ((N - n) * 1000) >= 4000) {
if(menu[n][1] > menu[n][0]) {
break;
}
answer += menu[n][0];
money -= 5000;
n++;
}
while (n < N) {
answer += menu[n][1];
n++;
}
System.out.println(answer);
}
}
