반응형

* Scanner와 BufferedReader 사용 방법

1
2
Scanner sc = new Scanner(System.in); 
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
cs


* BufferedReader 와 Scanner의 차이

 

 BufferedReader

Scanner 

Buffer 크기 

8192 Byte 

1024 Byte 

동기화 여부 

동기화  O  >> 멀티쓰레드에 적합

동기화 X 

Parsing 여부 

데이터 입력시 Parsing X

 데이터 입력시 Parsing O  >> 속도 저하

예외 처리 

I/O Exception 

예외를 숨긴다 


이러한 차이점을 가지고, 속도가 중요한 Algorithm 문제 풀이 시에는 되도록 BufferedReader를 사용하는 것이 바람직하다.

반응형
저작자표시 비영리 변경금지

'∙Algorithm Tech' 카테고리의 다른 글

[Algorithm Tech] 최단 경로 알고리즘  (0) 2019.01.16
[Algorithm Tech] 최소 신장 트리(MST, Minimum Spanning Tree)  (0) 2019.01.16
[Algorithm Tech] Dynamic Programming(동적 계획법)  (0) 2019.01.09
[Algorithm Tech] Binary Search(이분 탐색)  (0) 2019.01.08
반응형

* JVM(Java Virtual Machine)

JVM 역할은 자바 애플리케이션을 클래스 로더를 통해 읽어 들여 자바 API와 함께 실행하는 것

또한, Java와 OS 간의 중개자 역할을 수행하여 OS에 구애받지 않고 재사용을 가능하게 한다.

메모리관리 및 Garbage Collection 수행하며 Stack 기반의 가상머신이다.


* Java 프로그램 실행 과정


1. 프로그램이 실행되면 JVM은 OS로부터 이 프로그램이 필요로 하는 메모리를 할당받는다.

2. 자바 컴파일러(javac)가 자바 소스코드(.java)를 읽어들여 자바 바이트코드(.class)로 변환시킨다.

3. Class Loader를 통해 class파일들을 JVM으로 로딩한다.

4. 로딩된 class파일들은 Execution engine을 통해 해석된다.

5. 해석된 바이트코드는 Runtime Data Areas 에 배치되어 실질적인 수행이 이루어지게 된다.


* Class Loader(클래스 로더)

클래스 로더는 .class 파일을 읽어 바이트 코드를 메소드 영역(Method Area)에 저장한다.

 Runtime 시에 클래스를 처음으로 참조할 때, 해당 클래스를 로드하고 링크하는 역할을 수행한다.


* Runtime Data Area

프로그램 수행을 위해 os로부터 할당받는 메모리 영역으로 5가지로 볼 수 있다. 

# Method area 

클래스 정보를 처음 메모리 공간에 올릴 때 초기화되는 대상을 저장하기 위한 메모리공간이다.

클래스 이름, 부모 클래스 이름, 메소드, 변수 정보 등과 같은 수준의 모든 클래스 정보와 static 변수들을 저장한다. 

# Heap area

모든 객체를 저장하는 가상 메모리 공간이다. new 연산자로 생성된 객체와 배열을 저장한다.

# Stack area

프로그램 실행과정에서 임시로 할당되었다가 메소드를 빠져나가면 바로 소멸되는 특성의 데이터를 저장하기 위한 영역이다.

각종 형태의 변수나 임시 데이터, 스레드, 메소드 정보를 저장한다.

# PC Registers

Thread가 어떤 부분을 명령으로 실행해야할 지에 대한 기록을 하는 부분으로 현재 수행중인 JVM 명령의 주소를 가진다.

# Native Method Stacks

자바 프로그램이 컴파일되어 생성되는 실제 실행할 수 있는 기계어로 작성된 프로그램을 실행시키는 영역이다.


* Execution Engine(실행 엔진)

바이트 코드로 된 .class 파일을 실행한다. 바이트 코드를 한줄씩 읽고 다양한 메모리 영역에 나타난 데이터와 정보를 사용한다.

# Interpreter

실행 엔진은 바이트코드를 한줄씩 읽어서 실행한다. 단점은 여러번 하나의 메소드를 호출할 경우 매번 해석을 요청해야하기 때문에 비효율적이다. 

# JIT(Just-In-Time)

인터프리터 방식의 단점을 보완하기 위해 도입된 JIT 컴파일러이다.

전체 바이트 코드를 컴파일하고 네이티브 코드로 변경하여 더이상 인터프리팅 하지 않고 네이티브 코드로 직접 실행하는 방식이다.

JIT 컴파일러를 사용하는 JVM은 내부적으로 해당 메서드가 자주 수행되는지 체크하고, 일정 정도를 넘을 때 네이티브 코드로 변경한다.

# Garbage Collector

메모리 관리를 위한 방법 중의 하나로, Heap 영역 안의 Garbage를 찾아내서 Heap의 메모리를 회수한다.

참조되고 있지 않은 객체를 Garbage라고 하며, Garbage를 판별하기 위해 Reachability 개념을 사용한다.

한 객체가 다른 객체를 참조하며 다른 객체는 또다른 객체를 참조할 경우에는 유효한 최초의 참조가 무엇인지 파악해야 되는데, 이를 객체 참조의 root set이라고 한다.

  1. 힙 내의 다른 객체에 의한 참조 
  2. Java 스택, 즉 Java 메서드 실행 시에 사용하는 지역 변수와 파라미터들에 의한 참조 
  3. 네이티브 스택, 즉 JNI(Java Native Interface)에 의해 생성된 객체에 대한 참조 
  4. 메서드 영역의 정적 변수에 의한 참조

2, 3, 4번의 참조의 경우 root set이 되어 reachability를 판가름하는 기준이 된다. 

즉 root set으로부터 시작한 객체들은 reachable이며, root set과 무관한 객체들이 unreachable 객체로 GC의 대상이 된다.

## 참고) 메모리 누수 현상

컴퓨터 프로그램이 필요하지 않은 메모리를 계속 점유하고 있는 현상이다.

메모리 동적 할당시 Heap 영역에 할당되는데, 사용자가 해제하지 않는 경우 Heap 영역 메모리 공간을 계속 차지하게 된다.

이는 메모리 부족으로 시스템이 다운될 수도 있는 위험이 있다.

Java에서 Garbage Collector가 없다면 메모리 누수의 위험이 높다.


참조

http://asfirstalways.tistory.com/158

http://mygumi.tistory.com/115?category=648758

https://github.com/DaeHeeKim93/DaeHeeKim-Review/tree/master/Java/GC


반응형
저작자표시 비영리 변경금지

'∙Java' 카테고리의 다른 글

[Java] ==와 equals()의 차이  (0) 2019.01.10
[Java] Abstract Class와 Interface  (0) 2019.01.10
[Java] Stack 영역과 Heap 영역  (0) 2019.01.10
[Java] 왜 public static void main 이여야 할까?  (0) 2019.01.10
반응형

* 핵심

포도주를 연속으로 3잔을 마실 수 없다.

포도주를 연속으로 2잔을 안마시는 경우를 생각해야 한다. 

Ex) 100, 2, 1, 4, 100의 경우 204가 나와야 한다.


* 문제

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

  1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
  2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.


* 소스 코드 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int[] wine = new int[n + 1];
        int[][] dp = new int[10001][2];     //[x][?] : 이전에 방문한 포도주가 1칸 전에 있는지 or 2칸전에 있는지
 
        for (int i = 0; i < n; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }
        dp[0][0] = wine[0];
        dp[1][0] = wine[0] + wine[1];
        dp[1][1] = wine[1];
        if (n >= 2) {
            dp[2][0] = dp[1][1] + wine[2];
            dp[2][1] = dp[0][0] + wine[2];
            for (int i = 3; i <= n; i++) {      //목적지가 마지막이 아니기 때문에 n+1번 계산
                dp[i][0] = dp[i - 1][1] + wine[i];
                dp[i][1] = Math.max(dp[i - 3][0], Math.max(dp[i - 2][0], dp[i - 2][1])) + wine[i];
            }
        }
        System.out.println(Math.max(Math.max(dp[n][0], dp[n][1]), Math.max(dp[n - 1][0], dp[n - 1][1])));
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/11055 :: 가장 큰 증가 부분 수열  (0) 2019.01.14
[Algorithm] 백준/10835 :: 카드게임  (0) 2019.01.14
[Algorithm] 백준/1520 :: 내리막 길  (0) 2019.01.10
[Algorithm] 백준/9095 :: 1, 2, 3 더하기  (0) 2019.01.09
반응형

* 핵심

DFS에 DP를 결합한 문제

DFS로 목적지까지 도착하고 되돌아가면서 경우의 수를 추가해야 한다.

(1,1) -> (4,1) -> (4,5) -> (4,1) -> (1,1) -> (1,4) -> (4,4) -> (4,5) -> (4,4) -> (1,4) -> (1,5) -> (2,5) -> (2,4) -> (4,4) -> (4,5) -> (4,4) -> (1,4) -> (1,1)


* 문제

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.


* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.io.*;
import java.util.*;
 
public class Main {
    static int m, n;
    static int[][] map;
    static int[][] dp;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        m = Integer.parseInt(stk.nextToken());
        n = Integer.parseInt(stk.nextToken());
        map = new int[m][n];
        dp = new int[m][n];     // 각 지점에서 m,n까지 가는 경우의 수
 
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], -1);
        }
        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        System.out.println(dfs(0, 0));
    }
 
    public static int dfs(int x, int y) {
        if (x == m - 1 && y == n - 1) return 1;     //재귀 탈출조건
        if (dp[x][y] != -1) return dp[x][y];        //메모이제이션
        else {
            dp[x][y] = 0;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && map[x][y] > map[nx][ny]) {
                    dp[x][y] += dfs(nx, ny);        //dp[x][y]에 경우의 수 추가
                }
            }
            return dp[x][y];
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/10835 :: 카드게임  (0) 2019.01.14
[Algorithm] 백준/2156 :: 포도주 시식  (0) 2019.01.10
[Algorithm] 백준/9095 :: 1, 2, 3 더하기  (0) 2019.01.09
[Algorithm] 백준/1003 :: 피보나치 함수  (0) 2019.01.09
반응형

* 핵심

4의 경우 3가지의 경우의 수를 더한 값이 된다.

  • 3을 만드는 경우의 수 + 1
  • 2를 만드는 경우의 수 + 2
  • 1을 만드는 경우의 수 + 3

이를 점화식으로 나타내면,

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]


* 문제

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.


* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[12];
        Arrays.fill(dp, -1);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        while (n-- > 0) {
            int num = Integer.parseInt(br.readLine());
            for (int i = 4; i <= num; i++) {
                if (dp[i] != -1) continue;      //메모이제이션 사용
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
            }
            System.out.println(dp[num]);
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/2156 :: 포도주 시식  (0) 2019.01.10
[Algorithm] 백준/1520 :: 내리막 길  (0) 2019.01.10
[Algorithm] 백준/1003 :: 피보나치 함수  (0) 2019.01.09
[Algorithm] 백준/16469 :: 소년 점프  (0) 2019.01.09
반응형

* 핵심

Dynamic Programing 기법을 사용

Top-Down 방식 사용시에 메모이제이션 과정을 필수로 진행해야 한다.


* 문제

문제

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

  • fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
  • fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
  • 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
  • fibonacci(0)은 0을 출력하고, 0을 리턴한다.
  • fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
  • 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
  • fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.


* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.io.*;
import java.util.*;
 
public class Main {
    public static int[][] dp;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new int[41][2];     //[x][0] : x에서 사용된 0의 개수, [x][1] : x에서 사용된 1의 개수
        for (int i = 0; i <= 40; i++) {
            Arrays.fill(dp[i], -1);
        }
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;
 
        while (n-- > 0) {
            int num = Integer.parseInt(br.readLine());
            //Top-Down 방식
            fibo(num);
 
            //Buttom-Up 방식
            for (int i = 2; i <= num; i++) {
                dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
                dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
            }
            System.out.println(dp[num][0] + " " + dp[num][1]);
        }
    }
 
    public static int[] fibo(int n) {
        if (n <= 1) return dp[n];
        else {
            if (dp[n][0] == -1 && dp[n][1] == -1) {     //메모이제이션 사용(이미 계산한 값은 계산 x)
                dp[n][0] = fibo(n - 1)[0] + fibo(n - 2)[0];
                dp[n][1] = fibo(n - 1)[1] + fibo(n - 2)[1];
            }
            return dp[n];
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/1520 :: 내리막 길  (0) 2019.01.10
[Algorithm] 백준/9095 :: 1, 2, 3 더하기  (0) 2019.01.09
[Algorithm] 백준/16469 :: 소년 점프  (0) 2019.01.09
[Algorithm] 백준/1654 :: 랜선 자르기  (0) 2019.01.08
반응형

* Dynamic Programming(동적 계획법)

큰 문제를 작은 문제로 나눠서 푸는 알고리즘

큰 문제를 작은 문제로 나누는 방식은 Divide and Conquer(분할 정복) 방식과 비슷하지만 차이점이 있다.


분할 정복의 경우 결과가 한번만 사용되고, 분할하여 작은 문제를 푸는 것이 성능을 향상시키지만,

동적 계획법의 경우 결과가 여러번 사용되고, 결과를 재사용하여 성능을 향상시킨다.


DP의 핵심은 점화식을 어떻게 세우는지와 DP에 어떤 값을 메모이제이션 할 것인지를 정하는 것이다.

메모이제이션이란 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다.


* Dynamic Programing 문제를 푸는 방법

- Top-Down (재귀 사용)

큰 문제를 작은 문제로 나누어 결과값을 가지고 큰 문제를 푼다.

메모이제이션 작업을 필수로 진행해야 한다.


- Bottom-Up (For문 사용)

작은 문제를 풀어 결과값을 가지고 큰 문제를 푼다.


Dynamic Programing은 피보나치가 대표적인 예로 사용된다.

백준 1003 :: 피보나치 함수

반응형
저작자표시 비영리 변경금지

'∙Algorithm Tech' 카테고리의 다른 글

[Algorithm Tech] 최소 신장 트리(MST, Minimum Spanning Tree)  (0) 2019.01.16
[Algorithm Tech] Scanner vs BufferedReader  (0) 2019.01.10
[Algorithm Tech] Binary Search(이분 탐색)  (0) 2019.01.08
[Algorithm Tech] Divide and Conquer(분할 정복)  (0) 2019.01.08
반응형

* 핵심

악당 무리 3명이 같이 방문하는 점을 어떻게 찾을 것인지?

visited를 boolean이 아닌 int배열로 주고 for문을 돌면서 i 값마다 비트연산으로 확인함    >> 악당 3명이 방문한 점은 111 이니까 7이 된다.

TreeMap을 이용하여 최소 지점의 개수를 출력


* 문제

문제

한국 힙합의 떠오르는 신성인 마미손은 악당 무리에게서 도망치고 있다. 악당 무리는 넉살, 스윙스, 창모 3명으로 이루어져 있다. 마미손은 도망치는 도중 R*C 크기의 미로를 만났고, 미로 안에 숨기로 했다. 뒤늦게 미로에 도착한 악당 무리는 마미손을 찾기 위해 뿔뿔이 흩어져 찾아보기로 했다. 이때 악당들은 항상 상하좌우로만 이동 가능하고, 이동 속도는 모두 같으며 칸 단위로만 이동 가능하다. 또한 악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다. 넉살, 스윙스, 창모는 서로 다른 지점에서 마미손을 찾기 시작하는데 이들은 세 명이 한 지점에서 모였을 때 걸린 시간이 최소가 되는 지점에 마미손이 숨어있다고 확신한다. 마미손은 숨기 이전에 악당들이 어디서 탐색을 시작할지 알고 있어 악당들이 찾아올 지점들을 피해 숨으려고 한다. 

힘든 모험을 시작한 마미손. 이 모험에서 주인공은 절대 죽지 않는다는 것을 여러분이 마미손이 되어 보여주자! R*C 크기의 미로가 주어지고, 넉살, 스윙스, 창모의 시작 위치가 주어질 때, 한 지점에 세 악당이 모일 때 걸린 시간이 최소가 되는 지점을 마미손에게 알려주자. 

입력

첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다. (2 ≤ R, C ≤ 100) 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다. 숫자 0은 이동 가능한 길, 1은 벽을 나타낸다. 그 다음 줄부터 3개의 줄은 각각 넉살, 스윙스 창모의 위치(행, 열)를 나타내는 자연수 Xi, Yi가 (1 ≤ Xi ≤ R, 1 ≤ Yi ≤ C)주어진다. 악당들은 위치가 겹치지 않고, 항상 이동 가능한 길에서 출발한다. 맨 왼쪽 위의 위치는 (1, 1)이다. 

출력

첫째 줄에 한 지점에 세 악당이 모일 때 걸린 시간의 최소 값을 출력한다. 둘째 줄에는 그러한 지점의 개수를 출력한다. 만약 세 악당이 모일 수 있는 지점이 존재하지 않는다면 -1를 출력한다.


* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.io.*;
import java.util.*;
 
public class Main {
    public static int[][] map, res;
    public static int[][] visited;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1, -1, 0, 0};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
 
        int r = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());
 
        map = new int[r][c];
        res = new int[r][c];
        visited = new int[r][c];
 
        for (int i = 0; i < r; i++) {
            String s = br.readLine();
            for (int j = 0; j < s.length(); j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
 
        ArrayList<pair> badboy = new ArrayList<>();
 
        for (int i = 0; i < 3; i++) {
            stk = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(stk.nextToken());
            int y = Integer.parseInt(stk.nextToken());
            badboy.add(new pair(x - 1, y - 1, 0));
        }
        for (int i = 0; i < 3; i++) {
            pair p = badboy.get(i);
            Queue<pair> q = new LinkedList<>();
            q.add(new pair(p.x, p.y, 0));
            while (!q.isEmpty()) {
                p = q.poll();
                if ((visited[p.x][p.y] & 1 << i) == 0) {    // 비트 연산을 통한 악당 3명의 방문 여부 확인 
                    visited[p.x][p.y] += 1 << i;
                    res[p.x][p.y] = Math.max(res[p.x][p.y], p.w);
                    for (int j = 0; j < 4; j++) {
                        int nx = p.x + dx[j];
                        int ny = p.y + dy[j];
                        if (nx >= 0 && nx < r && ny >= 0 && ny < c && map[nx][ny] == 0)
                            q.add(new pair(nx, ny, p.w + 1));
                    }
                }
            }
        }
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (visited[i][j] == 7) {
                    if (tm.containsKey(res[i][j])) {
                        tm.put(res[i][j], tm.get(res[i][j]) + 1);
                    } else {
                        tm.put(res[i][j], 1);
                    }
                }
            }
        }
        if (tm.size() == 0) System.out.println("-1");
        else System.out.println(tm.firstEntry().getKey() + "\n" + tm.firstEntry().getValue());
    }
 
    public static class pair {
        int x, y, w;
 
        public pair(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/9095 :: 1, 2, 3 더하기  (0) 2019.01.09
[Algorithm] 백준/1003 :: 피보나치 함수  (0) 2019.01.09
[Algorithm] 백준/1654 :: 랜선 자르기  (0) 2019.01.08
[Algorithm] 백준/16564 :: 히오스 프로게이머  (0) 2019.01.08

티스토리툴바