백준 3055, 1600, 7576

이번에 문제를 풀 때는 Pos class 따로 만들지 않고 배열로 만들어서도 풀어봤다.

스터디원들이 내 준 문제들이 어째 다 골드여서.. 열심히 풀었다는 tmi... 

백준 3055 탈출 🦔

https://www.acmicpc.net/problem/3055

3055번: 탈출

🦔 바보같이 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번으로 제한이 있는 점이 이전에 푼 백준 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번: 토마토

 

🍅 전형적인 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;
    }
}