[SWEA] 2117. 홈 방범 서비스 - Simulation

제출일 : 2019-11-12

문제 풀이 시간 : 1H

난이도 : ★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

Constraints

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초

2. 도시의 크기 N은 5 이상 20 이하의 정수이다. (5 ≤ N ≤ 20)

3. 홈방범 서비스의 운영 비용은 서비스 영역의 면적과 동일하다.

4. 도시에는 최소 1개 이상의 집이 존재한다.

input

각 테스트 케이스의 첫 번째 줄에는 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M이 주어진다.

Output

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

출력해야 할 정답은 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때,

Example

input

10
8 3
0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0
1 0 0 0 0 0 0 0
…

output

#1 5
…

Solution & Inpression

모의 SW 역량테스트문제 중 가장 쉬웠던 문제인것 같다.

핵심은 마름모를 만드는것.
$$
if ((Math.abs(i - r) + Math.abs(j - c)) <= k - 1)
$$

Code

언어 : JAVA

메모리 : 45,780 kb

실행시간 : 499 ms

import java.util.Scanner;

public class Solution {
    static int N, M;
    static int[][] map;
    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt(); // 도시 크기
            M = sc.nextInt(); // 하나의 집이 지불할 수 있는 비용

            map = new int[N][N];
            int c = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int tmp = sc.nextInt();
                    map[i][j] = tmp; // 집이면 1
                    if (tmp == 1) {
                        c++;
                    }
                }
            }

            max = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (c == max)
                        break;
                    solve(i, j);
                }
            }

            System.out.println("#" + tc + " " + max);
        }
        sc.close();
    }

    private static void solve(int r, int c) {
        for (int k = 1; k <= N + N; k++) {
            int cnt = 0;
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    if ((Math.abs(i - r) + Math.abs(j - c)) <= k - 1)
                        if (map[i][j] == 1)
                            cnt++;

            int cost = k * k + (k - 1) * (k - 1);
            if (cost <= cnt * M)
                if (max < cnt)
                    max = cnt;
        }
    }

}

[SWEA] 5658. 보물상자 비밀번호 - Simulation

제출일 : 2019-09-03

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo

Input

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N과 크기 순서 K가 주어 진다.

그 다음 줄에는 16진수 0~F 숫자가 공백 없이 N개 주어진다.

Output

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

Example

input

5
12 10
1B3B3B81F75E
16 2
F53586D76286B2D8
…

output

#1 503
#2 55541
#3 334454
#4 5667473
#5 182189737

Code

언어 : JAVA

메모리 : 30,296 kb

실행시간 : 130ms

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

public class Solution {

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

        for (int tc = 1; tc <= T; tc++) {
            System.out.print("#" + tc + " ");
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int M = N / 4;
            ArrayList<Character> list = new ArrayList<>();
            String str = br.readLine();
            for (int i = 0; i < N; i++) {
                list.add(str.charAt(i));
            }
            ArrayList<String> numlist = new ArrayList<>();
            str = "";
            for (int i = 1; i <= N; i++) {
                str += list.get(i - 1);
                if (i % M == 0) {
                    if (!numlist.contains(str))
                        numlist.add(str);
                    str = "";
                }
            }

            for (int i = 1; i <= M - 1; i++) {
                char tmp = list.get(0);
                list.remove(0);
                list.add(tmp);
                str = "";
                for (int j = 1; j <= N; j++) {
                    str += list.get(j - 1);
                    if (j % M == 0) {
                        if (!numlist.contains(str))
                            numlist.add(str);
                        str = "";
                    }
                }
            }

            Collections.sort(numlist, new Comparator<String>() { // 역정렬
                @Override
                public int compare(String o1, String o2) {
                    int x = Integer.parseInt(o1, 16);
                    int y = Integer.parseInt(o2, 16);
                    return y - x;
                }
            });

            System.out.println(Integer.parseInt(numlist.get(K-1), 16));

        } // end of TC
    }// end of main
}

[SWEA] 6109. 추억의 2048게임 D4 - Simulation

제출일 : 2019-11-03

문제 풀이 시간 : 1H 30M

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbrg9uabZsDFAWQ

Input

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1≤N≤20)과 하나의 문자열 S가 공백 하나로 구분되어 주어진다.

S는 “left”, “right”, “up”, “down”의 넷 중 하나이며 각각 타일들을 왼쪽, 오른쪽, 위쪽, 아래쪽으로 이동시키겠다는 뜻이다.

다음 N개의 줄의 i번째 줄에는 N개의 정수가 공백 하나로 구분되어 주어진다.

이 정수들은 0이거나 2이상 1024이하의 2의 제곱수들이다.

i번째 줄의 j번째 정수는 격자의 위에서 i번째 줄의 왼쪽에서 j번째에 있는 칸에 있는 타일에 어떤 정수가 적혀 있는지 나타내며,

0이면 이 칸에 타일이 없음을 의미한다.

Output

각 테스트 케이스마다 ‘#t’(t는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고 한 줄을 띄운 후,

N줄에 걸쳐 격자의 어떤 위치에 어떤 숫자가 적힌 타일이 있는지 입력 형식과 같은 형식으로 출력한다.

Example

input

2
5 up
4 8 2 4 0
4 4 2 0 8
8 0 2 4 4
2 2 2 2 8
0 2 2 0 0
2 down
16 2
0 2

output

#1
8 8 4 8 8
8 4 4 2 4
2 4 2 0 8
0 0 0 0 0
0 0 0 0 0
#2
0 0
16 4

Solution & Inpression

시뮬레이션 문제

차근차근 구현하면 되는 문제......

Code

언어 : JAVA

메모리 : 73,768 kb

실행시간 : 363 ms

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();
            String cmd = sc.next();
            int[][] in = new int[N][N];
            int[][] out = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    in[i][j] = sc.nextInt();
                }
            }
            switch (cmd) {
            case "up":
                for (int j = 0; j < N; j++) { // 열 우선 탐색
                    for (int i = 0; i < N - 1; i++) { // 위부터 아래로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = i + 1;

                        while (in[idx][j] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == N - 1) // 끝까지 탐색
                                break;
                            idx++;
                        }

                        if (in[idx][j] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[idx][j]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[idx][j] = 0;
                            i = idx;
                        }
                    }
                    int cur = 0;
                    for (int i = 0; i < N; i++) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[cur++][j] = in[i][j];
                        }
                    }
                }
                break;
            case "down":
                for (int j = 0; j < N; j++) { // 열 우선 탐색
                    for (int i = N - 1; i > 0; i--) { // 아래부터 위
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = i - 1;

                        while (in[idx][j] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == 0) // 끝까지 탐색
                                break;
                            idx--;
                        }

                        if (in[idx][j] == 0) // 비교할 값이 0이면 패스
                            continue;
                        if (in[i][j] == in[idx][j]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[idx][j] = 0;
                            i = idx;
                        }

                    }
                    int cur = N - 1;
                    for (int i = N - 1; i >= 0; i--) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[cur--][j] = in[i][j];
                        }
                    }
                }
                break;
            case "left":
                for (int i = 0; i < N; i++) { // 행우선 탐색
                    for (int j = 0; j < N - 1; j++) { // 왼쪽부터 오른쪽으로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = j + 1;

                        while (in[i][idx] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == N - 1) // 끝까지 탐색
                                break;
                            idx++;
                        }

                        if (in[i][idx] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[i][idx]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[i][idx] = 0;
                            j = idx;
                        }
                    }
                    int cur = 0;
                    for (int j = 0; j < N; j++) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[i][cur++] = in[i][j];
                        }
                    }
                }
                break;

            case "right":
                for (int i = 0; i < N; i++) { // 행우선 탐색
                    for (int j = N-1; j > 0; j--) { // 오른쪽 부터 왼쪽으로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = j - 1;

                        while (in[i][idx] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == 0) // 끝까지 탐색
                                break;
                            idx--;
                        }

                        if (in[i][idx] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[i][idx]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[i][idx] = 0;
                            j = idx;
                        }
                    }
                    int cur = N-1;
                    for (int j = N-1; j >=0 ; j--) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[i][cur--] = in[i][j];
                        }
                    }
                }
                break;

            }

            System.out.println("#" + tc);
            for (int[] is : out) {
                for (int i : is) {
                    System.out.print(i + " ");
                }
                System.out.println();
            }

        } // end of TC
    }// end of Main
}

[SWEA] 5431. 민석이의 과제 체크하기 D3

제출일 : 2019-07-16

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWVl3rWKDBYDFAXm

Input

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

각 테스트 케이스의 첫 번째 줄에는 수강생의 수를 나타내는 정수 N(2≤N≤100)과 과제를 제출한 사람의 수를 나타내는 정수 K(1≤K≤N)가 공백으로 구분되어 주어진다.

두 번째 줄에는 과제를 제출한 사람의 번호 K개가 공백으로 구분되어 주어진다. 번호는 1이상 N이하의 정수이며 같은 번호가 두 번 이상 주어지는 경우는 없다.

Output

각 테스트 케이스마다 과제를 제출하지 않은 사람의 번호를 오름차순으로 출력한다.

Example

input

2
5 3
2 5 3
7 2
4 6

output

#1 1 4
#2 1 2 3 5 7

Code

언어 : JAVA

메모리 : 56,744 kb

실행시간 : 363 ms

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

public class Solution{
    public static void main(String args[]) throws Exception {
        //System.setIn(new FileInputStream("res/input_d3_5431.txt"));
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();

        for (int i = 0; i < N; i++) {

            int students = s.nextInt();
            int submit = s.nextInt();

            int[] mem = new int[students];

            for (int j = 0; j < submit; j++) {
                int temp = s.nextInt();
                mem[temp - 1]++;
            }
            System.out.print("#" + (i + 1) + " ");

            for (int j = 0; j < students; j++) {
                if (mem[j] == 0)
                    System.out.print((j + 1) + " ");
            }
            System.out.println();

        }

        s.close(); // Scanner close
    }
}

[SWEA] 1208. Flatten D3

제출일 : 2019-07-16

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh

Input

총 10개의 테스트 케이스가 주어지며, 각 테스트 케이스의 첫 번째 줄에는 덤프 횟수가 주어진다. 그리고 다음 줄에 각 상자의 높이값이 주어진다.

Output

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 최고점과 최저점의 높이 차를 출력한다.

Example

input

834
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 ...
617
16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 ...
...

output

#1 13
#2 32
...

Code

언어 : JAVA

메모리 : 23,404 kb

실행시간 : 178 ms

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

public class Solution{
    public static void main(String args[]) throws Exception {

        Scanner s = new Scanner(System.in);
        for (int tc = 1; tc <= 10; tc++) {
            int Dump = s.nextInt(); // 834

            int[] box = new int[100];

            for (int i = 0; i < 100; i++) {
                box[i] = s.nextInt();
            } 
            Arrays.sort(box);

            int head = 0;
            int tail = 99;
            while (true) {

                box[head]++;
                box[tail]--;
                Dump--;
                Arrays.sort(box);
                if (Dump == 0)
                    break;
            }

            System.out.println("#" + tc + " " + (box[99] - box[0]));
        }
        s.close(); // Scanner close
    }
}

[SWEA] 1204. 최빈수 구하기 D2

제출일 : 2019-07-16

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV13zo1KAAACFAYh

Input

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

각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호가 주어지고 그 다음 줄부터는 점수가 주어진다.

Output

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

Example

input

10
1
41 85 72 38 80 69 65 68 96 22 49 67 51 61 63 87 66 24 80 83 71 60 64 52 90 60 49 31 23 99 94 11 25 24 51 15 13 39 67 97 19 76 12 33 99 18 92 35 74 0 95 71 39 33 39 32 37 45 57 71 95 5 71 24 86 8 51 54 74 24 75 70 33 63 29 99 58 94 52 13 35 99 46 57 71 23 17 3 94 48 77 18 83 11 83 25 59 62 2 78 86 7 94 65 80 32 39 84 60 65 72 61 58 84 8 72 12 19 47 49 49 59 71 52 34 22 21 20 92 33 80 39 74 9 28 97 100 93 29 25 4 66 79 81 98 21 91 62 82 4 59 100 34 1 51 80 92 69 77 39 38 97 51 34 35 19 22 1 67 9 90 31 82 11 51 84 78 70 74 42 100 88 53 80 57 62 32 51 48 63 92 46 4 61 31 98 69 52 88 20 68 41 48 79 97 98 56 44 73 3 63 100 87 87 41 79 64 83 63 1 21 72 24 9 75 51 25 53 77 0 52 30 96 93 32 89 70 89 55 71 79 40 10 64 80 30 19 62 67 98 42 8 32 57 27 22 1 38 89 52 74 43 8 2 65 82 20 67 22 43 22 95 16 48 25 6 75 86 96 3 85 43 69 93 4 61 53 81 43 84 20 15 34 22 35 26 28 33 67 19 79 19 45 8 13 51 0 86 68 18 47 82 3 16 80 0 18 39 22 5 26 65 70 21 92 66 65 14 6 46 46 21 32 80 35 86 6 67 29 42 71 14 77 55 3 1 14 38 71 82 41 65 12 5 77 3 67 22 59 40 81 48 63 63 25 45 32 78 83 26 96 18 99 45 56 31 30 45 47 80 1 7 81 18 1 90 15 71 22 69 44 18 31 60 16 93 13 17 44 97 98 51 46 42 22 47 72 97 24 52 55 59 25 100 28 5 14 76 32 41 97 61 32 20 0 2 8 41 52 77 35 22 98 78 92 68 29 82 33 28 16 5 9 21 13 26 39 59 69 10 42 4 13 80 34 42 100 44 32 70 15 32 8 83 10 23 73 8 53 7 21 10 52 14 82 28 24 33 94 59 4 17 73 53 85 31 100 74 74 12 72 38 34 14 22 53 0 30 95 3 52 79 41 36 81 25 24 67 48 95 44 7 96 77 90 48 92 45 78 93 95 38 71 4 83 79 64 89 0 76 81 34 66 1 13 58 4 40 5 24 17 6 65 13 13 76 3 20 8 36 12 60 37 42 53 87 10 65 42 25 47 41 33 71 69 94 24 12 92 11 71 3 82 91 90 20 95 44 76 60 34 95 49 40 89 4 45 27 9 34 82 59 2 20 68 22 29 10 1 23 19 47 16 76 47 49 90 94 10 18 55 69 14 26 59 77 73 8 21 72 1 74 76 51 94 44 24 98 71 77 59 9 12 49 38 72 22 55 35 61 16 48 41 21 67 74 92 4 7 85 34 92 39 96 42 26 1 1 4 64 33 96 62 23 67 76 26 47 32 73 82 30 14 61 21 92 40 4 2 38 76 64 8 14 3 49 71 31 38 86 98 17 15 98 32 55 69 46 61 3 44 67 50 44 76 0 45 23 25 11 82 99 11 39 50 40 21 52 17 60 44 90 44 6 16 38 3 41 43 56 26 24 0 9 90 36 50 13 42 88 87 66 32 28 73 94 52 11 35 47 9 87 37 57 15 56 38 95 6 43 23 30 84 39 88 69 5 34 81 93 86 2 77 10 28 30 97 68 14 12 88 1 100 35 73 30 2 43 11 41 58 82 6 84 71 16 18 67 41 100 92 78 57 7 35 69 56 76 13 93 26 26 38 21 96 7 88 2 60 17 54 95 26 2 0 21 87 11 96 36 83 88 31 24 24 62 14 88 84 39 22 17 84 96 1 78 91 53 9 35 75 87 100 33 80 42 7 20 50 65 81 92 14 45 96 34 6 20 86 51 4 19 70 91 13 0 42 70 43 15 47 14 96 72 41 91 11 72 7 92 12 16 51 13 86 40 50 43 55 26 7 1 70 18 71 99 49 55 94 78 40 59 20 96 34 6 28 85 42 70 62 63 32 34 97 80 49 47 50 73 85 63 20 29 0 19 91 84 58 55 33 4 68 55 12 38 49 9 13 99 4 35 26 5 42 29 98 20 95 77 36 63 41 42 45 81 40 53 60 5 55 9 13 34 6 52 28 35 33 29 21 67 57 61 21 41 95 54 50 19 81 75 67 73 77 47 40 83 16 28
.......

output

#1 71
#2 76
.......

Code

언어 : JAVA

메모리 : 36,640 kb

실행시간 : 204 ms

import java.util.Arrays;
import java.util.Scanner;
import java.io.FileInputStream;

public class Solution{
    public static void main(String args[]) throws Exception {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();


        for (int i = 1; i <= N; i++) {
            int num = s.nextInt();
            int[] array = new int[1000]; 

            for (int j = 0; j < 1000; j++) { 
                array[j] = s.nextInt();
            }


            int[] countarray = new int[101];

            for (int j = 0; j < 1000; j++) {
                countarray[array[j]]++; 
            }

            int result = 0;
            int temp = 0;

            for (int j = 100; j >= 0; j--) {
                if (result < countarray[j]) {
                    result = countarray[j];
                    temp = j;
                }
            }

            System.out.println("#" + num + " " + temp);

        } 

    }

}

[SWEA] 7701. 염라대왕의 이름 정렬 D4 - TreeSet

제출일 : 2019-10-08

문제 풀이 시간 : 15M

난이도 : ★☆

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG

Input

첫 번째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 50)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 이승 명부의 이름 개수 N(1 ≤ N ≤ 20,000)이 주어진다.

각 테스트 케이스의 두 번째 줄부터 N개의 줄에 걸쳐서 알파벳 소문자로 이루어진 이름들이 주어진다.

이름에는 공백이 포함되지 않으며 최소 1개, 최대 50개의 알파벳으로 이루어져 있다.

Output

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

정리된 이름을 한 줄에 하나씩 출력하라. 같은 이름은 한 번만 출력해야 하는 것을 주의하라.

Example

input

2
5
my
name
is
ho
seok
12
s
a
m
s
u
n
g
j
j
a
n
g

output

#1
ho
is
my
name
seok
#2
a
g
j
m
n
s
u

Solution & Inpression

문제를 잘 읽고 문제에 맞추어 구현하면 되는 문제

Set, TreeSet, Comparator, comparTo등 자료구조와 함수를 알고 있다면 쉽게 해결할 수 있는 문제.

Code

언어 : JAVA

메모리 : 102,728 kb

실행시간 : 4,681 ms

import java.io.*;
import java.util.*;
public class Solution {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/D4_7701_염라대왕의이름정렬.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();

            Set<String> set = new TreeSet<>(new Comparator<String>() { 
                @Override
                public int compare(String o1, String o2) {
                    int r = o1.length() - o2.length();
                    if (r == 0)
                        return o1.compareTo(o2);
                    else
                        return r;
                }
            });

            for (int i = 0; i < N; i++) {
                set.add(sc.next());
            }

            System.out.println("#"+tc);

            for (String string : set) {
                System.out.println(string);
            }


        }
    }
}

[SWEA] 1249. 보급로 D4 - Dijkstra

제출일 : 2019-10-07

문제 풀이 시간 : 30M

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

Input

가장 첫 줄은 전체 테스트케이스의 수이다.

각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.

그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.

Output

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다.

이때 C는 케이스의 번호이다.

같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.

Example

input

10
4
0100
1110
1011
1010
6
011001
010100
010011
101001
010101
111010
8
. . .

output

#1 2
#2 2
. . .

Solution & Inpression

BFS로 이미 방문햇더라도 지금까지 계산한 값이 더작으면 queue에 담았습니다. >> 풀고나서 보니 다익스트라 알고리즘을 구현한것이었다.

code 1은 처음으로 구현한 풀이 방법이고

시간을 줄이기 위해 우선순위 큐를 사용하여 code 2를 작성하였다.

Code 1

언어 : JAVA

메모리 : 112,060 kb

실행시간 : 776 ms

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

public class Solution {
    static int N;
    static char[][] map;
    static int[][] mem;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/D4_1249_보급로.txt"));

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            map = new char[N][];
            mem = new int[N][N];

            for (int i = 0; i < N; i++) {
                map[i] = sc.next().toCharArray();
                Arrays.fill(mem[i], Integer.MAX_VALUE / 2);
            }

            Queue<int[]> q = new LinkedList<>();
            // 출발 = 0,0
            q.offer(new int[] { 0, 0, 0 });
            mem[0][0] = 0;
            while (!q.isEmpty()) {
                int[] tmp = q.poll();

                for (int k = 0; k < 4; k++) {
                    int r = tmp[0] + dr[k];
                    int c = tmp[1] + dc[k];
                    if (range(r, c)) {
                        int time = tmp[2] + Integer.parseInt("" + map[r][c]);
                        if (mem[r][c] > time) {
                            mem[r][c] = time;
                            q.offer(new int[] { r, c, mem[r][c] });
                        }
                    }
                }
            }
            System.out.println("#" + tc + " " + mem[N-1][N-1]);
        }
        sc.close();
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }
}

Code 2

언어 : JAVA

메모리 : 53,140 kb

실행시간 : 219 ms

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

public class Solution {
    static int N;
    static char[][] map;
    static int[][] mem;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/D4_1249_보급로.txt"));

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            map = new char[N][];
            mem = new int[N][N];

            for (int i = 0; i < N; i++) {
                map[i] = sc.next().toCharArray();
                Arrays.fill(mem[i], Integer.MAX_VALUE / 2);
            }

            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return Integer.compare(o1[2], o2[2]);
                }
            });
            // 출발 = 0,0
            pq.offer(new int[] { 0, 0, 0 });
            mem[0][0] = 0;
            while (!pq.isEmpty()) {
                int[] tmp = pq.poll();

                for (int k = 0; k < 4; k++) {
                    int r = tmp[0] + dr[k];
                    int c = tmp[1] + dc[k];
                    if (range(r, c)) {
                        int time = tmp[2] + Integer.parseInt("" + map[r][c]);
                        if (mem[r][c] > time) {
                            mem[r][c] = time;
                            pq.offer(new int[] { r, c, mem[r][c] });
                        }
                    }
                }
            }
            System.out.println("#" + tc + " " + mem[N-1][N-1]);
        }
        sc.close();
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }
}