백준 1027, 14502

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

1027번: 고층 건물

- 기울기 계산하는 공식이 필요한 문제 

- 처음에는 오른쪽 왼쪽 다 계산하게끔 만들었는데, 그럴 필요 없이 그냥 한 방향으로 쭉 탐색할 수 있었다. 

- 일단 이웃하는 애는 무조건 보이고, 내 쪽에서 보인다는 뜻은 반대편에서도 내 쪽이 보인다는 뜻이므로 한 방향으로 탐색할 때 양쪽을 같이 증가시켜주면 된다. 

 

이 문제는 진짜 ... 계속 뭐가 안 되는건지 원인을 잘 못찾아서 푸는데 오래 걸렸던 문제이다.

 

🏙 일단 slope 갱신 관련한 실수이다.

------ 처음에는 무조건 slope 갱신하도록 코드를 짰었다.

= 반례 )  빌딩 높이가  2 3 1 4 이런식으로 갈때 2의 입장에서 1은 어차피 3에 가려져서 안 보인다. 즉, 높이가 1인 빌딩을 바라볼 때 경사도가 아닌, 더 높은 값인 3보다 높은지 낮은지를 따져야 함
🏙 또한 slope 계산시 자료형 문제이다.

----- int형이 아닌, Double로 계산해주는 것 빼먹지 말것... 빌딩의 높이와 인덱스는 정수형이지만 계산 결과는 double로 따져야하므로.. 

 

import java.io.*;
import java.util.*;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        buildings = new int[n];
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            buildings[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < n-1; i++) {

            // 이웃하는 빌딩은 무조건 보임
            double slope = calculate(i, i+1);

            // answer[] ~ i는 i+1입장에서 보이므로 +1 (오른쪽에서 보이면 왼쪽도 반대로 볼 수 있다는 뜻)
            answer[i]++;
            answer[i+1]++;

            for (int j = i+2; j < n; j++) {
                double tempSlope = calculate(i, j);
                if (slope < tempSlope) {
                    slope = tempSlope; 
                    answer[i]++;
                    answer[j]++;
                }

            }

        }

        int highest = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            highest = Math.max(highest, answer[i]);
        }

        System.out.println(highest);

    }

    public static double calculate(int left, int right) {
        return (double) (buildings[right] - buildings[left])/ (right - left);
    }

}

---

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

14502번: 연구소

생각보다 금방 푼(?) 문제이다. 아마 이전에 연구소 시리즈 문제를 풀었어서 그런듯 하다. 전형적인 삼성st 기출문제이다. 

 

벽을 세울 수 있는 칸은 0인 칸이고, 2인 칸은 바이러스가 있는 칸이다. 

벽의 후보인 칸이랑, 바이러스 칸은 ArrayList에 미리 담아두었다. 

 

DFS 돌리면서 벽 후보 리스트에서 3칸 선정하고, 선정 끝나면 바이러스 퍼트리는 BFS 수행하면 된다. 

이 벽 세우는거랑 바이러스 퍼뜨리는 것도 당연히 원본배열 손대면 안된다. 

 

 

import java.util.*;
import java.io.*;
public class p14502 {
    static int[] dirX = { -1, 1, 0, 0};
    static int[] dirY = { 0, 0, -1, 1};
    static int[][] map;
    static int row;
    static int column;
    static int empty; // 빈 칸 개수
    static int answer;
    static ArrayList<Pos> canBeWall;
    static ArrayList<Pos> virus;
    static boolean[] selected;
    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());
        column = Integer.parseInt(st.nextToken());

        map = new int[row][column];
        canBeWall = new ArrayList<>();
        virus = new ArrayList<>();
        empty = 0;
        answer = Integer.MIN_VALUE;

        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < column; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 0) {
                    canBeWall.add(new Pos(i, j));
                    empty++;
                }
                else if (map[i][j] == 2) {
                    virus.add(new Pos(i, j));
                }
            }
        }
        selected = new boolean[empty];

        DFS(0, 0);
        System.out.println(answer);
    }

    public static int BFS() {
        Queue<Pos> queue = new LinkedList<>();
        boolean[][] visited = new boolean[row][column];
        int[][] temp = new int[row][column];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                temp[i][j] = map[i][j];
            }
        }

        // 가벽 세우기
        for (int i = 0; i < selected.length; i++) {
            if (!selected[i]) {
                continue;
            } else {
                Pos pos = canBeWall.get(i);
                temp[pos.x][pos.y] = 1;
            }
        }

        int count = 0;
        for (Pos pos : virus) {
            queue.add(pos);
        }

        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 (!isValid(nextX, nextY)) {
                    continue;
                }
                if (visited[nextX][nextY]) {
                    continue;
                }

                if (temp[nextX][nextY] == 1) {
                    continue;
                }

                queue.add(new Pos(nextX, nextY));
                temp[nextX][nextY] = 2;
                visited[nextX][nextY] = true;
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (temp[i][j] == 0) {
                    count++;
                }
            }
        }

        return count;
    }

    public static void DFS(int cur, int depth) {
        if (depth == 3) {
            answer = Math.max(BFS(), answer);
            return;
        }
        for (int i = cur; i < empty; i++) {
            selected[i] = true;
            DFS(i+1, depth+1);
            selected[i] = false;
        }
    }

    public static boolean isValid(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < column;
    }

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