Java/코딩테스트
백준 3055, 1600, 7576
Bubbles
2023. 8. 30. 02:54
이번에 문제를 풀 때는 Pos class 따로 만들지 않고 배열로 만들어서도 풀어봤다.
스터디원들이 내 준 문제들이 어째 다 골드여서.. 열심히 풀었다는 tmi...
백준 3055 탈출 🦔
https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
🦔 바보같이 S가 비버의 굴...인줄 알고 풀었다. 답이 계속 이상하길래 헤맸다...ㅋㅋ
🦔 물 먼저 퍼트리고, 그 다음 고슴도치를 이동시킨다. 원래 각각에 해당하는 temp 리스트를 만들까 했는데, 메모리가 옹졸하다. 그래서 계속 물 / 고슴도치 BFS 돌리기 전에 size 구한 다음, 그 만큼만 돌리는 방식으로 구현하였다.
🦔 고슴도치가 갈 수 있는 공간이 남아있을 때까지 반복 / 더 이상 이동할 수 없다면 while문 반복을 종료하고 나온다.
🦔 이 버전을 각각 Pos, Animal class 구현해서 제출 해봤는데, 메모리를 조금 더 쓰고 시간을 아낄수 있었다.
import java.util.*;
import java.io.*;
public class p3055 {
private static int row, col;
private static char[][] map;
private static int[] dirX = { -1, 1, 0, 0 };
private static int[] dirY = { 0, 0, -1, 1 };
private static Queue<int[]> waterPos;
private static Queue<int[]> animalPos;
private static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
row = Integer.parseInt(st.nextToken());
col = Integer.parseInt(st.nextToken());
waterPos = new LinkedList<>();
animalPos = new LinkedList<>();
map = new char[row][col];
answer = Integer.MAX_VALUE;
for (int i = 0; i < row; i++) {
String str = br.readLine();
for (int j = 0; j < col; j++) {
map[i][j] = str.charAt(j);
if (map[i][j] == 'S') {
animalPos.add(new int[]{i, j, 0});
}
else if (map[i][j] == '*') {
waterPos.add(new int[] { i, j });
}
}
}
BFS();
if (answer == Integer.MAX_VALUE) {
System.out.println("KAKTUS");
} else {
System.out.println(answer);
}
}
private static void BFS() {
while (!animalPos.isEmpty()) {
int size = waterPos.size();
for (int w = 0; w < size; w++) {
int[] waterPoll = waterPos.poll();
for (int i = 0; i < 4; i++) {
int nextX = waterPoll[0] + dirX[i];
int nextY = waterPoll[1] + dirY[i];
if (isValid(nextX, nextY)) {
if (map[nextX][nextY] == '.' || map[nextX][nextY] == 'S') {
map[nextX][nextY] = '*';
waterPos.add(new int[] {nextX, nextY});
}
}
}
}
// 고슴도치
size = animalPos.size();
for (int m = 0; m < size; m++) {
int[] poll = animalPos.poll();
for (int i = 0; i < 4; i++) {
int nextX = poll[0] + dirX[i];
int nextY = poll[1] + dirY[i];
if (isValid(nextX, nextY)) {
if (map[nextX][nextY] == 'D') {
answer = Math.min(answer, poll[2] + 1);
return;
}
else if (map[nextX][nextY] == '.') {
map[nextX][nextY] = 'S';
animalPos.add(new int[] {nextX, nextY, poll[2] + 1});
}
}
}
}
}
}
private static boolean isValid(int x, int y) {
if (x < 0 || x >= row || y < 0 || y >= col) {
return false;
}
return true;
}
}
백준 1600 말이 되고픈 원숭이 🐵
https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
🐵 말처럼 행동할 수 있는 경우가 K번으로 제한이 있는 점이 이전에 푼 백준 14442 - 벽 뚫고 가기랑 비슷하다.
🐵 상하좌우 움직임 + 말이 움직일 수 있는 8가지도 미리 정의를 해 두었다.
🐵 말처럼 행동 가능한 횟수를 안 넘겼다면 말 처럼 행동하는 반경에도 방문 처리하기
🐵 방문 배열은 몇 번 말처럼 행동해서 온 건지 정보도 담아야 해서 3차원 배열로 선언해두었다.
import java.io.*;
import java.util.*;
public class p1600 {
private static int k, row, col, answer;
private static int[][][] visit;
private static int[][] map;
private static int[] dirX = { -1, 1, 0, 0 };
private static int[] dirY = { 0, 0, -1, 1 };
private static int[] horseX = { -2, -2, -1, 1, 2, 2, 1, -1 };
private static int[] horseY = { -1, 1, 2, 2, 1, -1, -2, -2 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
col = Integer.parseInt(st.nextToken());
row = Integer.parseInt(st.nextToken());
map = new int[row][col];
visit = new int[row][col][k+1];
answer = -1;
for (int i = 0; i < row; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
BFS();
System.out.println(answer);
}
private static void BFS() {
Queue<Pos> queue = new LinkedList<>();
queue.add(new Pos(0, 0, 0));
visit[0][0][0] = 1;
while (!queue.isEmpty()) {
Pos poll = queue.poll();
if (poll.x == row-1 && poll.y == col-1) {
int temp = Integer.MAX_VALUE;
for (int i = 0; i <= k; i++) {
if (visit[row-1][col-1][i] != 0) {
temp = Math.min(temp, visit[row-1][col-1][i]-1);
}
}
if (temp != Integer.MAX_VALUE) {
answer = temp;
}
break;
}
for (int i = 0; i < 4; i++) {
int nextX = poll.x + dirX[i];
int nextY = poll.y + dirY[i];
if (isValid(nextX, nextY)) {
if (map[nextX][nextY] == 1) {
continue;
}
if (visit[nextX][nextY][poll.horseMove] == 0) {
visit[nextX][nextY][poll.horseMove] = visit[poll.x][poll.y][poll.horseMove] + 1;
queue.add(new Pos(nextX, nextY, poll.horseMove));
}
}
}
if (poll.horseMove < k) {
for (int i = 0; i < 8; i++) {
int nextX = poll.x + horseX[i];
int nextY = poll.y + horseY[i];
if (isValid(nextX, nextY)) {
if (map[nextX][nextY] == 1) {
continue;
}
if (visit[nextX][nextY][poll.horseMove + 1] == 0) {
visit[nextX][nextY][poll.horseMove + 1] = visit[poll.x][poll.y][poll.horseMove] + 1;
queue.add(new Pos(nextX, nextY, poll.horseMove+1));
}
}
}
}
}
}
private static boolean isValid(int x, int y) {
if (x < 0 || x >= row || y < 0 || y >= col) {
return false;
}
return true;
}
private static class Pos {
int x;
int y;
int horseMove;
public Pos(int x, int y, int horseMove) {
this.x = x;
this.y = y;
this.horseMove = horseMove;
}
}
}
백준 7576 토마토 🍅
https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
🍅 전형적인 BFS 문제
🍅 처음부터 토마토가 모두 익은 상태로 주어지는 경우도 있으므로 안 익은 토마토 개수만 먼저 세고, 0일 경우 BFS 수행하지 말기
🍅 익어있는 토마토만 reds 리스트에 담아두었다가 BFS수행 시 큐에 다 넣고 거기서부터 BFS 시작하기
🍅 마지막에 결과 출력시에 -1을 해줘야 한다. 처음 익어있는 토마토를 1로 두고 시작했기 때문에 마지막에 -1하기.
import java.util.*;
import java.io.*;
public class p7576 {
private static int row, col, all;
private static List<int[]> reds;
private static int[][] tomato;
private static int[] dirX = { -1, 1, 0, 0 };
private static int[] dirY = { 0, 0, -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
col = Integer.parseInt(st.nextToken());
row = Integer.parseInt(st.nextToken());
all = 0;
tomato = new int[row][col];
reds = new ArrayList<>();
for (int i = 0; i < row; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
tomato[i][j] = Integer.parseInt(st.nextToken());
if (tomato[i][j] == 1) {
reds.add(new int[] {i, j});
}
else if (tomato[i][j] == 0) {
all++;
}
}
}
if (all == 0) {
System.out.println(0);
return;
}
BFS();
if (all == 0) {
System.out.println(count()-1);
} else {
System.out.println(-1);
}
}
private static int count() {
int answer = Integer.MIN_VALUE;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (tomato[i][j] > answer) {
answer = tomato[i][j];
}
}
}
return answer;
}
private static void BFS() {
Queue<int[]> queue = new LinkedList<>(reds);
while (!queue.isEmpty()) {
int[] poll = queue.poll();
for (int i = 0; i < 4; i++) {
int nextX = poll[0] + dirX[i];
int nextY = poll[1] + dirY[i];
if (!isValid(nextX, nextY)) {
continue;
}
if (tomato[nextX][nextY] == 0) {
tomato[nextX][nextY] = tomato[poll[0]][poll[1]] + 1;
all--;
queue.add(new int[] {nextX, nextY});
}
}
}
}
private static boolean isValid(int x, int y) {
if (x < 0 || x >= row || y < 0 || y >= col) {
return false;
}
return true;
}
}