프로그래머스 - 단속카메라, 백준 13549, 5427
🚨 프로그래머스 : 단속카메라
https://school.programmers.co.kr/learn/courses/30/lessons/42884
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
🚨그리디 알고리즘 문제
🚨진입 / 진출 지점에서 만난 것도 만난 것으로 인정하므로 구간 끝에 카메라를 설치한다고 생각하면 된다.
🚨여기서 진입 지점으로 정렬할지 진출 지점으로 정렬할지 헷갈렸는데 진출 시점으로 정렬해야 한다. 첫 구간이 아주 길다면 내부 구간이 다 무시되기 때문이다.
🚨그림 설명
🚨전체코드
참고로 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
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
🛝 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번: 불
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에
www.acmicpc.net
🔥백준 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;
}
}
}