서로 다른 점(친구들의 위치) 세개가 주어지고 meeting point를 정해 친구들이 움직인 거리의 합이 최소가 되도록 하는 문제.
어이없게 A번을 pretest #3에서 틀려서 빠른 멘붕...
점 세개길래 신나서 평균때리고 계산해서 제출했는데 그냥 최대-최소 하면 되는거였다. 중간 위치의 친구가 있는 곳에서 만나면 됨.
평균으로 하면 중복해서 움직이는 거리가 생기더라... 멘붕상태라 이걸 빨리 못찾고 5분은 헤맨거 같다.
import java.util.Scanner;
public class ProblemA {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x1 = sc.nextInt();
int x2 = sc.nextInt();
int x3 = sc.nextInt();
int min = x1;
int max = x1;
if (x2 < min) min = x2;
if (x2 > max) max = x2;
if (x3 < min) min = x3;
if (x3 > max) max = x3;
System.out.println(max-min);
}
}
호수를 나타내는 지도가 문자열로 주어지는데, 여기서 최소한의 땅을 메꿔서 k개의 호수만 남기는 문제. 처음 주어지는 지도에서는 k개 이상의 호수가 있는게 보장되기 때문에 호수를 늘리진 않는다. 처음에 조건을 끝까지 안봤을 때는 호수 중간의 허리같은 땅을 메꿔서 하나를 두개로 만들고... 이런 변태적인 상황을 생각해서 못풀것만 같았는데 호수를 줄여나가는 문제라서 그런걸 고려할 필요가 없다는걸 깨닫고 희망차게(!) 풀이를 시작했다.
먼저 테두리쪽에 붙어있는 호수가 아닌애들을 색출해내고, 그다음에 호수를 차례로 방문하면서 넓이를 구한다. 상하좌우 재귀탐색을 통해서 호수 하나의 넓이를 구해낼 수 있다. 그리고 호수를 우선순위큐에 넣어서 남는게 k개가 될 때까지 넓이가 작은 것 순으로 하나씩 끄집어낸다. 큐에서 꺼내진 호수를 메꾸면 끝- 메꾸는 과정도 넓이 구하는 것과 비슷하게 할 수 있다. 메꾸는 작업을 위해서 Lake 클래스에 포함된 점하나 정보를 넣어놓았다ㅎㅎ
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class ProblemD {
static int n, m, k;
static char[][] map;
static boolean[][] visited;
static int curArea;
static class Lake implements Comparable<Lake> {
int startX;
int startY;
int area;
Lake (int startX, int startY, int area) {
this.startX = startX;
this.startY = startY;
this.area = area;
}
@Override
public int compareTo(Lake lake) {
return Integer.compare(this.area, lake.area);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] tmp = br.readLine().split(" ");
n = Integer.parseInt(tmp[0]);
m = Integer.parseInt(tmp[1]);
k = Integer.parseInt(tmp[2]);
map = new char[n][m];
visited = new boolean[n][m];
for (int i=0; i<n; i++) {
map[i] = br.readLine().toCharArray();
}
curArea = 0;
for (int i=0; i<m; i++) {
if (!visited[0][i] && map[0][i] == '.') findArea(0, i);
if (!visited[n-1][i] && map[n-1][i] == '.') findArea(n-1, i);
}
for (int i=0; i<n; i++) {
if (!visited[i][0] && map[i][0] == '.') findArea(i, 0);
if (!visited[i][m-1] && map[i][m-1] == '.') findArea(i, m-1);
}
PriorityQueue<Lake> lakes = new PriorityQueue<Lake>();
for (int i=1; i<n-1; i++) {
for (int j=1; j<m-1; j++) {
if (!visited[i][j] && map[i][j] == '.') {
curArea = 0;
findArea(i, j);
lakes.add(new Lake(i, j, curArea));
}
}
}
int res = 0;
while (lakes.size() > k) {
Lake cur = lakes.poll();
fill(cur.startX, cur.startY);
res += cur.area;
}
System.out.println(res);
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
private static void fill(int x, int y) {
map[x][y] = '*';
if (x > 0 && map[x-1][y] == '.') fill(x-1, y);
if (x < n-1 && map[x+1][y] == '.') fill(x+1, y);
if (y > 0 && map[x][y-1] == '.') fill(x, y-1);
if (y < m-1 && map[x][y+1] == '.') fill(x, y+1);
}
private static void findArea(int x, int y) {
visited[x][y] = true;
curArea++;
if (x > 0 && !visited[x-1][y] && map[x-1][y] == '.') findArea(x-1, y);
if (x < n-1 && !visited[x+1][y] && map[x+1][y] == '.') findArea(x+1, y);
if (y > 0 && !visited[x][y-1] && map[x][y-1] == '.') findArea(x, y-1);
if (y < m-1 && !visited[x][y+1] && map[x][y+1] == '.') findArea(x, y+1);
}
}
