Algorithm
비숍
문제
서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.
< 그림 1 >
그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.
< 그림 2 >
< 그림 3 >
정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.
출력
첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.
예제 입력 1
5
1 1 0 1 1
0 1 0 0 0
1 0 1 0 1
1 0 0 0 0
1 0 1 1 1
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
// 비숍의 성질: 같은 칸만 이동할 수 있다
// 다른 색의 칸은 고려할 필요 없음 -> 시간 단축
public class one1799 {
/// 하얀 비숍들이 들어갈 수 있는 칸
private List<int[]> whitePoints;
// 하얀색 칸에 놓을 수 있는 비숍의 최대 갯수
private int whiteMax;
// 검은 비숍들이 들어갈 수 있는 칸
private List<int[]> blackPoints;
// 검은색 칸에 놓을 수 있는 비숍의 최대 갯수
private int blackMax;
public int solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(reader.readLine());
whitePoints = new ArrayList<>();
whiteMax = 0;
blackPoints = new ArrayList<>();
blackMax = 0;
for (int i = 0; i < size; i++) {
StringTokenizer boardToken = new StringTokenizer(reader.readLine());
for (int j = 0; j < size; j++) {
// 비숍이 놓일 수 있는 칸이다.
if (Integer.parseInt(boardToken.nextToken()) == 1) {
// 검은색이냐 하얀색이냐
if ((i + j) % 2 == 0) whitePoints.add(new int[]{i, j});
else blackPoints.add(new int[]{i, j});
}
}
}
dfsWhite(0, new boolean[whitePoints.size()]);
dfsBlack(0, new boolean[blackPoints.size()]);
return whiteMax + blackMax;
}
// 하얀색 비숍을 DFS 하는 함수
private void dfsWhite(
// 다음에 고려할 비숍이 놓일 칸
// 의 whitePoints 인덱스
int next,
// 몇번째 비숍 칸들을 선택했는지
boolean[] selected
) {
// 종료조건 next == whitePoints.size()
if (next == whitePoints.size()) {
// 이번에 완성한 비숍들이 총 몇개가 쓰였는지
int count = 0;
for (boolean select: selected) {
if (select) count += 1;
}
// 최댓값 갱신
whiteMax = Math.max(whiteMax, count);
}
// 탐색하기
else {
selected[next] = true;
// 다음 단계로 넘어가기 전에 가망성 조사를 해야한다.
if (checkWhite(next, selected)) dfsWhite(next + 1, selected);
selected[next] = false;
dfsWhite(next + 1, selected);
}
}
// 하얀색 비숍들이 서로 공격하지 못하는지 확인하는 함수
private boolean checkWhite(int next, boolean[] selected) {
// 마지막으로 선택한 비숍
int[] point = whitePoints.get(next);
for (int i = 0; i < next; i++) {
if (
selected[i] &&
Math.abs(whitePoints.get(i)[0] - point[0]) ==
Math.abs(whitePoints.get(i)[1] - point[1])
) return false;
}
return true;
}
// 검은색 비숍을 DFS 하는 함수
private void dfsBlack(
// 다음에 고려할 비숍이 놓일 칸
// 의 blackPoints 인덱스
int next,
// 몇번째 비숍 칸들을 선택했는지
boolean[] selected
) {
// 종료조건 next == whitePoints.size()
if (next == blackPoints.size()) {
// 이번에 완성한 비숍들이 총 몇개가 쓰였는지
int count = 0;
for (boolean select: selected) {
if (select) count += 1;
}
// 최댓값 갱신
blackMax = Math.max(blackMax, count);
}
// 탐색하기
else {
selected[next] = true;
// 다음 단계로 넘어가기 전에 가망성 조사를 해야한다.
if (checkBlack(next, selected)) dfsBlack(next + 1, selected);
selected[next] = false;
dfsBlack(next + 1, selected);
}
}
// 검은색 비숍들이 서로 공격하지 못하는지 확인하는 함수
private boolean checkBlack(int next, boolean[] selected) {
// 마지막으로 선택한 비숍
int[] point = blackPoints.get(next);
for (int i = 0; i < next; i++) {
if (
selected[i] &&
Math.abs(blackPoints.get(i)[0] - point[0]) ==
Math.abs(blackPoints.get(i)[1] - point[1])
) return false;
}
return true;
}
public static void main(String[] args) throws IOException {
System.out.println(new one1799().solution());
}
}치즈
문제
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
<그림 1> 원래 치즈 모양
다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
<그림 2> 한 시간 후의 치즈 모양
<그림 3> 두 시간 후의 치즈 모양
<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
예제 입력 1
13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// https://www.acmicpc.net/problem/2636
public class four2636 {
// foreach 구문 사용을 위해 한 큐에
private final int[][] deltas = new int[][] {
new int[] {-1, 0},
new int[] {1, 0},
new int[] {0, -1},
new int[] {0, 1},
};
private void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer colRowToken = new StringTokenizer(reader.readLine());
int y = Integer.parseInt(colRowToken.nextToken());
int x = Integer.parseInt(colRowToken.nextToken());
int cheeseCount = 0;
int lastCheese = 0;
int[][] board = new int[y][x];
for (int i = 0; i < y; i++) {
StringTokenizer rowToken = new StringTokenizer(reader.readLine());
for (int j = 0; j < x; j++) {
board[i][j] = Integer.parseInt(rowToken.nextToken());
if (board[i][j] == 1) cheeseCount++;
}
}
boolean[][] visited = new boolean[y][x];
// 몇 시간이 지났는지
int reps = 0;
Queue<int[]> thisVisit = new LinkedList<>();
thisVisit.add(new int[] {0, 0});
// 치즈가 남아 있는 동안
while (cheeseCount > 0) {
reps++;
// 치즈를 만나면 이번이 아닌 다음 번에 주변을 살펴 봐야 하기 때문에
// thisVisit과 분리
Queue<int[]> nextVisit = new LinkedList<>();
Queue<int[]> nextMelt = new LinkedList<>();
// 치즈를 만나면 멈추었을 때
// 현재 방문 가능한 점들을 방문하는 반복문
while (!thisVisit.isEmpty()) {
int[] now = thisVisit.poll();
for (int[] delta: deltas) {
int nextY = now[0] - delta[0];
int nextX = now[1] - delta[1];
if (-1 < nextX && nextX < x
&& -1 < nextY && nextY < y
&& !visited[nextY][nextX]
) {
visited[nextY][nextX] = true;
int[] next = new int[] {nextY, nextX};
// 다음 방문할 곳이 치즈다
if (board[nextY][nextX] == 1) {
nextMelt.add(next);
nextVisit.add(next);
}
// 아니라면 이번에 방문할 곳
else {
thisVisit.add(next);
}
}
}
}
// 이번에 어떤 치즈가 녹을지 알아냈다
// 다음 시간에 적용하자
// 다음 시간에 방문할 곳 지정
thisVisit = nextVisit;
// 현재 치즈의 개수가 정답에서 요구하는
// 직전 시간의 치즈 갯수일 가능성이 높다
lastCheese = cheeseCount;
// 남아 있는 치즈의 개수 계산
cheeseCount -= nextMelt.size();
while(!nextMelt.isEmpty()) {
int[] melt = nextMelt.poll();
board[melt[0]][melt[1]] = 0;
}
}
System.out.println(reps);
System.out.println(lastCheese);
}
public static void main(String[] args) throws IOException {
new four2636().solution();
}
}탈출
문제
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
입력
첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.
출력
첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.
예제 입력 1
3 3
D.*
...
.S.
예제 입력 2
3 3
D.*
...
..S
예제 입력 3
3 6
D...*.
.X.X..
....S.
예제 입력 4
5 4
.D.*
....
..X.
S.*.
....
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
//https://www.acmicpc.net/problem/3055
public class four3055 {
private int row;
private int col;
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer rowColToken = new StringTokenizer(reader.readLine());
row = Integer.parseInt(rowColToken.nextToken());
col = Integer.parseInt(rowColToken.nextToken());
char[][] board = new char[row][];
boolean[][] visited = new boolean[row][col];
int[][] deltas = new int[][] {
new int[]{-1, 0},
new int[]{1, 0},
new int[]{0, -1},
new int[]{0, 1}
};
// 회차마다 다음번 방문할 예정인 점을 기록
Queue<int[]> nextVisit = new LinkedList<>();
// 회차마다 다음번 물이 들어찰 예정인 점을 기록
Queue<int[]> nextWater = new LinkedList<>();
for (int i = 0; i < row; i++) {
board[i] = reader.readLine().toCharArray();
for (int j = 0; j < col; j++) {
// 시작 지점일 경우
if (board[i][j] == 'S')
nextVisit.add(new int[]{i, j});
// 물의 근원인 경우
else if (board[i][j] == '*')
nextWater.add(new int[]{i, j});
}
}
// 고슴도치 목적지 도착 표시용
boolean success = false;
// 몇번째 시행인지
int reps = 0;
while (!success) {
reps += 1;
// 이번에 방문할 물 칸 들
Queue<int[]> thisWater = nextWater;
nextWater = new LinkedList<>();
while (!thisWater.isEmpty()) {
int[] now = thisWater.poll();
for (int[] delta: deltas) {
int nextY = now[0] - delta[0];
int nextX = now[1] - delta[1];
if (checkBounds(nextX, nextY)
&& (board[nextY][nextX] == '.' || board[nextY][nextX] == 'S')
) {
board[nextY][nextX] = '*';
nextWater.add(new int[]{nextY, nextX});
}
}
}
// 이번에 방문할 고슴도치 점
Queue<int[]> thisVisit = nextVisit;
nextVisit = new LinkedList<>();
while (!thisVisit.isEmpty()) {
int[] now = thisVisit.poll();
for (int[] delta: deltas) {
int nextY = now[0] - delta[0];
int nextX = now[1] - delta[1];
if (checkBounds(nextX, nextY) && !visited[nextY][nextX]) {
if (board[nextY][nextX] == '.') {
visited[nextY][nextX] = true;
nextVisit.add(new int[]{nextY, nextX});
}
else if (board[nextY][nextX] == 'D') {
success = true;
}
}
}
if (success) break;
}
// 다음 방문할 곳이 없다면
if (nextVisit.isEmpty()) {
break;
}
}
if (!success) System.out.println("KAKTUS");
else System.out.println(reps);
}
private boolean checkBounds(int x, int y) {
return (-1 < y && y < row && -1 < x && x < col);
}
public static void main(String[] args) throws IOException {
new four3055().solution();
}
}스타트 택시
문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
<그림 1>
<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.
<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.
<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.
<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.
입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
예제 입력 1
6 3 15
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5
예제 입력 2
6 3 13
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5
예제 입력 3
6 3 100
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
//https://www.acmicpc.net/problem/19238
public class two19238 {
private int size;
public int solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer infoToken = new StringTokenizer(reader.readLine());
size = Integer.parseInt(infoToken.nextToken());
int goalCount = Integer.parseInt(infoToken.nextToken());
int fuel = Integer.parseInt(infoToken.nextToken());
int[][] map = new int[size][size];
for (int i = 0; i < size; i++) {
StringTokenizer rowToken = new StringTokenizer(reader.readLine());
for (int j = 0; j < size; j++) {
if (Integer.parseInt(rowToken.nextToken()) == 1) map[i][j] = 1;
}
}
StringTokenizer startToken = new StringTokenizer(reader.readLine());
int[] start = new int[]{
Integer.parseInt(startToken.nextToken()) - 1,
Integer.parseInt(startToken.nextToken()) - 1
};
int[][] customers = new int[goalCount][];
int[][] goals = new int[goalCount][];
for (int i = 0; i < goalCount; i++) {
StringTokenizer customerToken = new StringTokenizer(reader.readLine());
customers[i] = new int[]{
Integer.parseInt(customerToken.nextToken()) - 1,
Integer.parseInt(customerToken.nextToken()) - 1
};
goals[i] = new int[]{
Integer.parseInt(customerToken.nextToken()) - 1,
Integer.parseInt(customerToken.nextToken()) - 1
};
}
int[][] deltas = new int[][]{
new int[]{-1, 0},
new int[]{1, 0},
new int[]{0, -1},
new int[]{0, 1},
};
boolean[] done = new boolean[goalCount];
while (!finished(done)) {
boolean[][] visited = new boolean[size][size];
visited[start[0]][start[1]] = true;
Queue<int[]> toVisit = new LinkedList<>();
toVisit.add(new int[]{start[0], start[1], 0});
boolean meetCustomer = false;
int nearCustomerIdx = -1;
int nearCustomerDist = 0;
// 고객한테 간다.
while (!toVisit.isEmpty()) {
int[] now = toVisit.poll();
int isCustomer = isCustomer(customers, now);
if (isCustomer != -1 && !done[isCustomer]){
// 이번 회차에서 최초로 만난 손님
if (!meetCustomer) {
meetCustomer = true;
nearCustomerIdx = isCustomer;
nearCustomerDist = now[2];
}
// 이미 이번 회차에서 손님 만난 적 있음
// 그중 좀더 빨리 만나는 경우 (는 사실 없다)
else if (nearCustomerDist > now[2]){
nearCustomerIdx = isCustomer;
}
// 같은 경우 행 후 열 찾기
else if (nearCustomerDist == now[2]) {
// 지금 행이 더 작다
if (now[0] > customers[nearCustomerIdx][0])
continue;
// 새로운 행이 더 작다
else if (now[0] < customers[nearCustomerIdx][0]) {
nearCustomerIdx = isCustomer;
}
// 동일하면 열 비교
else if (now[1] > customers[nearCustomerIdx][1]){
continue;
}
else {
nearCustomerIdx = isCustomer;
}
}
// 늦게 만난 경우는 그냥 스킵
}
// 손님을 만난 상태면 더이상 탐색하지 않는다.
if(!meetCustomer) for (int[] delta: deltas) {
int nextY = now[0] + delta[0];
int nextX = now[1] + delta[1];
if (
checkBounds(nextX, nextY) &&
map[nextY][nextX] == 0 &&
!visited[nextY][nextX]
) {
visited[nextY][nextX] = true;
toVisit.add(new int[]{nextY, nextX, now[2] + 1});
}
}
}
// 손님을 못만났다
if (nearCustomerIdx == -1) break;
// 연료가 부족하다
fuel -= nearCustomerDist;
if (!(fuel > 0)) break;
// 방문 기록 초기화
visited = new boolean[size][size];
// 고객을 목적지로
// 고객의 위치가 시작지점
toVisit.add(new int[]{
customers[nearCustomerIdx][0],
customers[nearCustomerIdx][1],
0
});
// 목적지를 다음 시작지점으로 설정 해둔다.
start = goals[nearCustomerIdx];
int goalDist = 0;
while (!toVisit.isEmpty()) {
int[] now = toVisit.poll();
if (now[0] == start[0] && now[1] == start[1]) {
goalDist = now[2];
break;
}
for (int[] delta: deltas) {
int nextY = now[0] + delta[0];
int nextX = now[1] + delta[1];
if (
checkBounds(nextX, nextY) &&
map[nextY][nextX] == 0 &&
!visited[nextY][nextX]
) {
visited[nextY][nextX] = true;
toVisit.add(new int[]{nextY, nextX, now[2] + 1});
}
}
}
// 도착하지 못해서 기름값 갱신이 없었다.
if (goalDist == 0) break;
// 도착하기 전에 연료가 다한다.
fuel -= goalDist;
if (fuel < 0) break;
// 도착해서 충전
else fuel += (goalDist * 2);
done[nearCustomerIdx] = true;
}
if (finished(done)) return fuel;
return -1;
}
private boolean finished(boolean[] doneList) {
for (boolean done: doneList)
if (!done) return false;
return true;
}
private int isCustomer(int[][] customers, int[] point) {
for (int i = 0; i < customers.length; i++) {
int[] customer = customers[i];
if (point[0] == customer[0] && point[1] == customer[1])
return i;
}
return -1;
}
private boolean checkBounds(int x, int y){
return -1 < x && x < size && -1 < y && y < size;
}
public static void main(String[] args) throws IOException {
System.out.println(new two19238().solution());
}
}JavaScript
JavaScript
JavaScript는 HTML, CSS와 더불어 Internet Cornerstone과 같은 역할을 한다. HTML은 어떤 내용을 어떤 구조로 담고 있는지를 결정하고, CSS는 표현 방식과 디자인 혹은 배치와 애니메이션 등을 표현한다. 그렇다면 JavaScript의 역할은 무엇일까? 일반적으로 동작을 정의한다. 예를 들어 버튼을 눌렀을 때 창이 변하거나 색이 변하거나 다크 모드 등등의 동작을 표현하며 HTML의 내용을 바꾸도록 해 주는 것이 JavaScript의 역할이다. 정적 데이터인 HTML, CSS에 비해 동적 컨텐츠를 다루는 것이 JavaScript이다. 웹 브라우저에서 해석하여 웹 브라우저가 로드한 HTML 문서를 조작, 사용자의 행동에 따라 UI의 변화를 일으키는 프로그래밍 언어라고 생각하면 된다. 단순 정보 제공을 위해 사용되던 Web이 어플리케이션, 채팅 등의 기능을 할 수 있게 해 준 기술이다. 사전에 기계어로 번역되지 않고 필요한 순간에 브라우저로 인해 해석되는 스크립트 언어라고 볼 수 있다. 특히 Node.js의 등장과 함께 백엔드 언어로도 활용되며 그 인기가 높아졌다.
Java와는 아무런 관계가 없다. 표면적으로 문법이 유사하긴 하지만 유사성을 찾기란 어렵다.
Node.js
JavaScript는 웹 브라우저에서 사용한다. 그러나 이를 컴퓨터에서는 사용하지 못할까? Google Chrome은 V8이라는 JavaScript Engine 사용하며 성능에 힘입어 높은 점유율을 이끌었다. 이 V8을 브라우저에서 분리하고 서버에서 사용할 수 있도록 만든 것이 Node.js이다. Node.js는 Java Bytecode의 JVM, JRE 같은 역할을 한다. Node.js 자체는 프레임워크가 아니고 Runtime Envorionment라고 보는 것이 더욱 적합하다.
