프로그래머스 - 단속카메라, 백준 13549, 5427

🚨 프로그래머스 : 단속카메라

https://school.programmers.co.kr/learn/courses/30/lessons/42884

프로그래머스

 

🚨그리디 알고리즘 문제

 

🚨진입 / 진출 지점에서 만난 것도 만난 것으로 인정하므로 구간 끝에 카메라를 설치한다고 생각하면 된다. 

🚨여기서 진입 지점으로 정렬할지 진출 지점으로 정렬할지 헷갈렸는데 진출 시점으로 정렬해야 한다. 첫 구간이 아주 길다면 내부 구간이 다 무시되기 때문이다. 

 

🚨그림 설명

 

🚨전체코드

참고로 pivot은 이 구간의 최솟값이 -30000이라 -30001로 초기화하였다. 

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        PriorityQueue<Route> queue = new PriorityQueue<>((o1, o2) -> o1.end - o2.end);
        
        for (int[] route : routes) {
            queue.add(new Route(route[0], route[1]));
        }
        
        int answer = 0;
        int pivot = -30001;
        while (!queue.isEmpty()) {
            Route route = queue.poll();
            if (route.start > pivot) {
                pivot = route.end;
                answer++;
            }
        }
        return answer;
    }
    
    class Route {
        int start;
        int end;
        Route(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

 

 

---

 

 

🛝 백준 13549 : 숨바꼭질 3

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

13549번: 숨바꼭질 3

 

🛝 BFS 알고리즘 문제

 

🛝 수빈 위치와 동생 위치가 같다면 바로 0 출력해주고 끝난다. 

🛝 방문 배열에 방문 처리 하고, 최단 시간 찾는 것이므로 BFS로 풀면 된다.

🛝 순간이동 한 경우 / 걸은 경우 시간은 다르게 표현해줘야 하며, 배열의 인덱스를 넘어가지 않도록 if 조건 분기만 잘 나누어주면 어렵지 않게 풀 수 있다 

 

🛝 전체코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class p13549 {
    public static void main(String[] args) {
        int[] arr = new int[100001];
        boolean[] visited = new boolean[100001];
        Scanner sc = new Scanner(System.in);
        Queue<Integer> queue = new LinkedList<>();

        int n = sc.nextInt();
        int k = sc.nextInt();
        queue.add(n);
        visited[n] = true;
        arr[n] = 1;
        if (n == k) {
            System.out.println(0);
            return;
        }

        while (!queue.isEmpty()) {
            int poll = queue.poll();
            if (poll == k) {
                System.out.println(arr[poll] -1);
                break;
            }

            if (poll <= 50000 && !visited[poll*2]) {
                arr[poll*2] = arr[poll];
                visited[poll*2] = true;
                queue.add(poll*2);
            }
            if (poll > 0 && !visited[poll-1]) {
                arr[poll-1] = arr[poll] + 1;
                visited[poll-1] = true;
                queue.add(poll-1);
            }
            if (poll < 100000 && !visited[poll+1]) {
                arr[poll+1] = arr[poll] + 1;
                visited[poll+1] = true;
                queue.add(poll+1);
            }

        }
    }
}

 

 

---

 

 

 

🔥 백준 5427 : 불

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

5427번: 불

 

🔥백준 4179번 - 불! 과 느낌표 하나 차이로 다른 문제가 있어서 풀어봤다. 

🔥동일하게 BFS 문제이다. 

 

🔥불이 아예 없는 경우(fires.isEmpty())인 경우 불 BFS 돌리지 않도록 하기 

🔥불이 있어도 불 자체가 벽으로 둘러쌓여서 못 퍼지는 경우 있을 수도 있다. 이 경우 visitied 값이 0이라 탈출 못한걸로 판정나는 실수가 있었는데, 그래서 마지막 정답 비교조건에서 불길이 아예 닿지 않았거나, 나의 도착시간이 불보다 빠른 경우에 정답을 갱신하도록 만들었다. 

🔥이 2가지 예외처리만 잘 해준다면 이전에 풀었던 문제와 유사한 문제였다. 

 

🔥전체코드

import java.io.*;
import java.util.*;
public class p5427 {
    private static char[][] map;
    private static int[][] visited;
    private static int[] dirX = { 0, 0, 1, -1 }; // 동서남북
    private static int[] dirY = { 1, -1, 0, 0 };
    private static int row, col;
    private static Pos me;
    private static List<Pos> fires;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            col = Integer.parseInt(st.nextToken());
            row = Integer.parseInt(st.nextToken());

            map = new char[row][col];
            visited = new int[row][col];
            fires = new ArrayList<>();

            for (int j = 0; j < row; j++) {
                String line = br.readLine();
                for (int k = 0; k < col; k++) {
                    map[j][k] = line.charAt(k);
                    if (map[j][k] == '@') {
                        me = new Pos(j, k);
                    }
                    else if (map[j][k] == '*') {
                        fires.add(new Pos(j, k));
                    }
                }
            }

            int answer = BFS();
            if (answer == Integer.MAX_VALUE) {
                System.out.println("IMPOSSIBLE");
            } else {
                System.out.println(answer);
            }
        }

    }


    private static int BFS() {
        int answer = Integer.MAX_VALUE;
        Map<Pos, Integer> time = new HashMap<>();
        Queue<Pos> queue = new LinkedList<>();

        queue.add(me);
        visited[me.x][me.y] = 1;
        while (!queue.isEmpty()) {
            Pos poll = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = poll.x + dirX[i];
                int nextY = poll.y + dirY[i];

                if (nextX < 0|| nextX >= row || nextY < 0 || nextY >= col) {
                    time.put(new Pos(poll.x, poll.y), visited[poll.x][poll.y]);
                    continue;
                }

                if (map[nextX][nextY] != '.') {
                    continue;
                }

                if (visited[nextX][nextY] != 0) {
                    continue;
                }

                queue.add(new Pos(nextX, nextY));
                visited[nextX][nextY] = visited[poll.x][poll.y] + 1;
            }
        }

        if (fires.isEmpty()) {
            for (Integer i : time.values()) {
                answer = Math.min(answer, i);
            }
            return answer;
        }

        // 불 퍼트리기
        queue = new LinkedList<>();
        visited = new int[row][col];
        queue.addAll(fires);
        for (Pos p : fires) {
            visited[p.x][p.y] = 1;
        }


        while (!queue.isEmpty()) {
            Pos poll = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = poll.x + dirX[i];
                int nextY = poll.y + dirY[i];

                if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
                    continue;
                }

                if (map[nextX][nextY] == '#') {
                    continue;
                }

                if (visited[nextX][nextY] != 0) {
                    continue;
                }

                queue.add(new Pos(nextX, nextY));
                visited[nextX][nextY] = visited[poll.x][poll.y] + 1;
            }
        }

        for (Pos pos : time.keySet()) {
            if (visited[pos.x][pos.y] == 0 || time.get(pos) < visited[pos.x][pos.y]) {
                answer = Math.min(answer, time.get(pos));
            }
        }


        return answer;
    }

    private static class Pos {
        int x;
        int y;

        public Pos (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}