잠시라도 밖에 있으면 육수가 줄줄 흐르는 날씨에 지쳐 집 밖으로 나갈 생각조차 안 하는 1인. 에어컨 시원하게 맞춰놓고 알고리즘 문제를 풀고 있노라면 이보다 행복할 수가 있을까? 점점 이성을 놓게 되는 7월의 마지막 주를 되돌아본다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Input ip = getInput(br);
Solution s = new Solution();
System.out.println(s.solution(ip.board, ip.target));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private static Input getInput(BufferedReader br) throws IOException {
int[] tokens = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int len = tokens[0];
int target = tokens[1];
int[][] board = new int[len][len];
for (int i = 0; i < board.length; i++) {
board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
return new Input(target, board);
}
private static class Input {
int target;
int[][] board;
public Input(int target, int[][] board) {
this.target = target;
this.board = board;
}
}
}
class Solution {
public int solution(int[][] board, int target) {
Calculator c = new Calculator(board, target);
return c.getResult();
}
}
class Calculator {
int[][] board;
int target;
int[] selectedChickens;
int result = Integer.MAX_VALUE;
List<Point> houses = new ArrayList<>();
List<Point> chickens = new ArrayList<>();
public Calculator(int[][] board, int target) {
this.board = board;
this.target = target;
this.selectedChickens = new int[target];
}
public int getResult() {
init();
select(0, 0);
return result;
}
private void init() {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if(board[i][j] == 1) houses.add(new Point(i, j));
else if (board[i][j] == 2) chickens.add(new Point(i, j));
}
}
}
public void select(int numOfSelected, int shopNum) {
if (numOfSelected == target) {
calc();
} else {
for (int i = shopNum; i < chickens.size(); i++) {
selectedChickens[numOfSelected] = i;
select(numOfSelected + 1, i + 1);
}
}
}
private void calc() {
int sum = 0;
for (Point house : houses) {
int chickenDistance = Integer.MAX_VALUE;
for (int i : selectedChickens) {
Point selectedChicken = chickens.get(i);
int distance = Math.abs(house.x - selectedChicken.x) + Math.abs(house.y - selectedChicken.y);
chickenDistance = Math.min(chickenDistance, distance);
}
sum += chickenDistance;
}
result = Math.min(result, sum);
}
private static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Solution s = new Solution();
System.out.println(s.solution(getInput(br)));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private static int[] getInput(BufferedReader br) throws IOException {
int len = Integer.parseInt(br.readLine());
int[] result = new int[len];
for (int i = 0; i < result.length; i++) {
result[i] = Integer.parseInt(br.readLine());
}
return result;
}
}
class Solution {
MidHeap mh = new MidHeap();
public String solution(int[] nums) {
StringBuilder result = new StringBuilder();
for(int num : nums){
mh.add(num);
result.append(mh.getMidNum()).append("\n");
}
return result.toString();
}
}
class MidHeap {
PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> minQ = new PriorityQueue<>();
public void add(int num) {
if (maxQ.size() >= minQ.size()) {
maxQ.add(num);
minQ.add(maxQ.poll());
} else {
minQ.add(num);
maxQ.add(minQ.poll());
}
}
public int getMidNum() {
if(maxQ.isEmpty() || maxQ.size() < minQ.size()) return minQ.peek();
return maxQ.peek();
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Solution s = new Solution();
System.out.println(s.solution(getInput(br)));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private static String[][] getInput(BufferedReader br) throws IOException {
String[] dimensions = br.readLine().split(" ");
int x = Integer.parseInt(dimensions[0]);
int y = Integer.parseInt(dimensions[1]);
String[][] field = new String[x][y];
for (int i = 0; i < field.length; i++) {
field[i] = br.readLine().split("");
}
return field;
}
}
class Solution {
public String solution(String[][] field) {
SeekAndHide sh = new SeekAndHide(field);
return sh.getResult();
}
}
class SeekAndHide {
String[][] field;
boolean[][] isChecked;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int sheepSurvived = 0;
int wolvesSurvived = 0;
public SeekAndHide(String[][] field) {
this.field = field;
this.isChecked = new boolean[field.length][field[0].length];
}
public String getResult() {
explore();
return sheepSurvived + " " + wolvesSurvived;
}
private void explore() {
for (int i = 0; i < field.length; i++) {
for (int j = 0; j < field[i].length; j++) {
if (!field[i][j].equals("#") && !isChecked[i][j]) {
isChecked[i][j] = true;
seekAndHide(i, j);
}
}
}
}
private void seekAndHide(int x, int y) {
int wolves = 0;
int sheep = 0;
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{x, y});
while (!q.isEmpty()) {
int[] cur = q.poll();
int curX = cur[0];
int curY = cur[1];
if(field[curX][curY].equals("v")) wolves++;
else if(field[curX][curY].equals("k")) sheep++;
for (int[] direction : directions) {
int nx = curX + direction[0];
int ny = curY + direction[1];
if (isWithinField(nx, ny) && !isChecked[nx][ny] && !field[nx][ny].equals("#")) {
isChecked[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
if(sheep > wolves) sheepSurvived += sheep;
else wolvesSurvived += wolves;
}
private boolean isWithinField(int x, int y) {
return 0 <= x && x < field.length && 0 <= y && y < field[x].length;
}
}