Slow And Steady Wins The Race

알고리즘 : 브루트포스

<그림 1>과 같이 9×9 격자판에 쓰여진 81개의 자연수 또는 0이 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.

예를 들어, 다음과 같이 81개의 수가 주어지면

이들 중 최댓값은 90이고, 이 값은 5행 7열에 위치한다.

입력

첫째 줄부터 아홉 번째 줄까지 한 줄에 아홉 개씩 수가 주어진다. 주어지는 수는 100보다 작은 자연수 또는 0이다.

출력

첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다.

예제 입력 1

3 23 85 34 17 74 25 52 65
10 7 39 42 88 52 14 72 63
87 42 18 78 53 45 18 84 53
34 28 64 85 12 16 75 36 55
21 77 45 35 28 75 90 76 1
25 87 65 15 28 11 37 28 74
65 27 75 41 7 89 78 64 39
47 47 70 45 23 65 3 41 44
87 13 82 38 31 12 29 29 80

예제 출력 1

90
5 7

백준 : https://www.acmicpc.net/problem/2566

알고리즘 : 기본정수론

소수구하기

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력

3 16

예제 출력

3
5
7
11
13

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

public class Main {
    private static int M;
    private static int N;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        printPrime();
    }
    private static void printPrime() {
        for(int i=M;i<=N;i++) {
            if(i==1) continue;
            else if(isPrime(i)) {
                System.out.println(i);
            }
        }
    }
    private static boolean isPrime(int num) {
        // 1과 나 자신만으로만 나누어지는지 확인.
        for(int i=2;i<Math.sqrt(num);i++) {
            if(num % i == 0) return false;
        }
        return true;
    }
}

알고리즘 : 브루트포스

색종이

평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 중 하나이다. 그림-1은 1번, 2번, 3번 세 장의 색종이가 순서대로 놓인 상태를 보여준다.

여기에 그림-2에서 보인 것처럼 4번 색종이가 하나 더 놓이면 3번 색종이는 완전히 가려서 보이지 않게 된다. 그리고, 1번 색종이와 2번 색종이는 부분적으로 가려 보이며, 4번 색종이는 완전히 보이게 된다.

N장의 색종이가 주어진 위치에 차례로 놓일 경우, 각 색종이가 보이는 부분의 면적을 구하는 프로그램을 작성하시오. 

입력

입력의 첫 번째 줄에는 색종이의 장수를 나타내는 정수 N (1 ≤ N ≤ 100)이 주어진다. 이어서 N장의 색종이에 관한 입력이 각 색종이마다 한 줄씩 차례로 주어진다. 색종이가 놓이는 평면은 가로 최대 1001칸, 세로 최대 1001칸으로 구성된 격자 모양이다. 격자의 각 칸은 가로, 세로 길이가 1인 면적이 1인 정사각형이다.

편의상 가로 6칸, 세로 6칸으로 이루어진 격자의 예를 들어 설명하면, 각 칸에 표시된 값 (a,b)는 해당 칸의 번호를 나타낸다. 가장 왼쪽 아래의 칸은 (0,0) 가장 오른 쪽 위의 칸은 (5,5)이다. 

색종이가 놓인 상태는 가장 왼쪽 아래 칸의 번호와 너비, 높이를 나타내는 네 정수로 표현한다. 예를 들어, 위 그림에서 회색으로 표시된 색종이는 (1,4)가 가장 왼쪽 아래에 있고 너비 3, 높이 2이므로 1 4 3 2로 표현한다. 색종이가 격자 경계 밖으로 나가는 경우는 없다. 

출력

입력에서 주어진 순서에 따라 N장의 색종이를 평면에 놓았을 때, 입력에서 주어진 순서대로 각 색종이가 보이는 부분의 면적을 한 줄에 하나씩 하나의 정수로 출력한다. 만약 색종이가 보이지 않는다면 정수 0을 출력한다. 

예제 입력 1

2
0 0 10 10
2 2 6 6

예제 출력 1

64
36

예제 입력 2

3
0 2 10 10
7 9 8 4
8 4 10 6

예제 출력 2

81
25
60

예제 입력 3

4
0 2 10 10
7 9 8 4
8 4 10 6
6 0 12 10

예제 출력 3

62
24
0
120

아래 2가지 사항에 대해서 깊이 생각해 보고 구현해야 함.

- 첫째, x, y 시작점을 어떻게 표현할 것인가?

- 둘째, 면적을 어떻게 표현할 것인가?

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

public class Main {
    private static int N;
    private static final int MAX = 1001;
    private static int[][] area = new int[MAX][MAX];
    private static int[] sum = new int[101];
    private static int width;
    private static int height;
    private static int x;
    private static int y;
    
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            y = Integer.parseInt(st.nextToken());
            x = MAX -1 -Integer.parseInt(st.nextToken());
            height = Integer.parseInt(st.nextToken());
            width = Integer.parseInt(st.nextToken());
            
            getArea(i);
        }
        calculate();
        print();
    }
    
    private static void getArea(int num) {
        int toX = x-width;
        int toY = y+height;
        for(int i=x;i>toX;i--) {
            for(int j=y;j<toY;j++) {
                area[i][j] = num;
            }
        }
    }
    
    private static void calculate() {
        for(int i=0;i<MAX;i++) {
            for(int j=0;j<MAX;j++) {
                if(area[i][j] > 0) {
                    sum[area[i][j]] = sum[area[i][j]] + 1;
                }
            }
        }
    }
    
    private static void print() {
        for(int i=1;i<=N;i++) {
            System.out.println(sum[i]);
        }
    }
    
}

참고

- 백준 10163번 : https://www.acmicpc.net/problem/10163

알고리즘 : BFS

문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

입력

N M
Hx Hy
Ex Ey
N X M 행렬

• 2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
• 1 ≤ Hx, Hy, Ex, Ey ≤ 1000
• (Hx, Hy)≠ (Ex, Ey)
• 행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

출력

D (탈출 할 수 없다면, -1을 출력한다.)

예제 입력 1

5 6
1 1
5 6
0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 0 0 1 1 0

예제 출력 2

11

힌트

제일 왼쪽 위 위치에서 제일 오른쪽 아래 위치로 이동하려면 (3,2) 벽을 파괴하고 이동하면 된다.

주의사항

- 방문 여부를 체크 함에 있어 마법의 지팡이를 사용했는지 여부도 포함시켜야 한다.

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

public class Main {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    
    private static int answer = -1;
    
    public static class Node {
        private int x;
        private int y;
        private int d;
        private boolean force;
        
        public Node(int x, int y, int d, boolean force) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.force = force;
        }
        public int getX() {
            return this.x;
        }
        public int getY() {
            return this.y;
        }
        public int getD() {
            return this.d;
        }
        public boolean getForce() {
            return this.force;
        }
        
    }
    
    public static boolean[][][] visited;
    public static int[][] mapInfo;
    
    public static int targetX;
    public static int targetY;
    
    public static int N;
    public static int M;
    
    public static int sX;
    public static int sY;
    
    public static boolean check(int x, int y) {
        if(x > 0 && y > 0 && x <= N && y <= M) return true;
        return false;
    }
    
    public static void bfs(Node start) {
        Queue<Node> q = new LinkedList<>();
        q.offer(start);
        visited[start.getX()][start.getY()][start.getForce() ? 1 : 0] = true;
        while(!q.isEmpty()) {
            Node cur = q.poll();
            if(cur.getX() == targetX && cur.getY() == targetY) {
                answer = cur.getD();
                break;
            }
           
            for(int i=0;i<4;i++) {
                int nextX = cur.getX() + dx[i];
                int nextY = cur.getY() + dy[i];
                if(check(nextX, nextY) && !visited[nextX][nextY][cur.getForce() ? 1 : 0]) {
                    if(mapInfo[nextX][nextY] == 0) { // 벽이 아닌 경우.
                        Node next = new Node(nextX, nextY, cur.getD()+1, cur.getForce());
                        q.offer(next);
                        visited[nextX][nextY][cur.getForce() ? 1 : 0] = true;
                    } else { // 벽인 경우.
                        if(!cur.getForce()) {
                           Node next = new Node(nextX, nextY, cur.getD()+1, true);
                           q.offer(next);
                           visited[nextX][nextY][1] = true; 
                        }
                    }
                }
            }
        }
    }
    
    public static void main(String args[]) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      
      mapInfo = new int[N+1][M+1];
      visited = new boolean[N+1][M+1][2];
      
      st = new StringTokenizer(br.readLine());
      
      sX = Integer.parseInt(st.nextToken());
      sY = Integer.parseInt(st.nextToken());
      
      st = new StringTokenizer(br.readLine());
      
      targetX = Integer.parseInt(st.nextToken());
      targetY = Integer.parseInt(st.nextToken());
      
      for(int i=1; i<=N; i++) {
          st = new StringTokenizer(br.readLine());
          for(int j=1; j<=M; j++) {
              mapInfo[i][j] = Integer.parseInt(st.nextToken());
          }
      }
      
      Node start;
      
      if(mapInfo[sX][sY] == 0) {
         start = new Node(sX, sY, 0, false);
      } else {
         start = new Node(sX, sY, 0, true);
      }
      
      bfs(start);
      
      System.out.println(answer);
    }
}

참고

- BFS : https://www.youtube.com/watch?v=CJiF-muKz30&t=197s

- 백준 14923 : https://www.acmicpc.net/problem/14923