[BOJ] 1157. 단어공부 - Array

제출일 : 2019-10-08

문제 풀이 시간 : 5M

난이도 : ☆

Problem

link : https://www.acmicpc.net/problem/17472

Input

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.

Output

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

Example

input

Mississipi

output

?

Solution & Inpression

알파벳은 26개

Code

언어 : JAVA

메모리 : 32,220 kb

실행시간 : 332 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] arr = sc.next().toUpperCase().toCharArray();

        int[] cnt = new int[26];

        for (int i = 0; i < arr.length; i++) {
            cnt[arr[i]-'A']++;
        }
        int max = -1;
        int maxIdx = -1;
        for (int i = 0; i < cnt.length; i++) {
            if(max<cnt[i]) {
                max = cnt[i];
                maxIdx = i;
            }
        }

        for (int i = 0; i < cnt.length; i++) {
            if(maxIdx!=i) {
                if(max==cnt[i]) {
                    System.out.println("?");
                    return;
                }            
            }
        }

        System.out.println((char)('A'+maxIdx));
    }
}

[BOJ] 17472. 다리 만들기2 - Prim

제출일 : 2019-10-07

문제 풀이 시간 : 45M

난이도 : ★★★★

Problem

link : https://www.acmicpc.net/problem/17472

Input

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

Output

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

Example

input

7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

output

9

Solution & Inpression

문제 풀이 순서

1. 섬을 구분한다

섬의 개수를 파악하하고 그래프를 그리기 위해 섬을 분리하는 작업을 진행한다.

BFS를 이용하여 섬을 라벨링 했다.

2. 그래프를 생성한다.

섬의 개수(정점)의 그래프를 생성한다.

3. 생성된 그래프의 간선을 연결한다.

섬을 잇는 간선을 찾아 연결한다. 이때 다리의 길이는 최소 2이상이어야 한다.

4. 최소신장트리를 이용하여 결과 값을 찾는다.

프림 알고리즘을 이용하여 최소신장트리를 구하고 이때의가중치의 합(결과값)을 찾는다.

모든 정점이 연결되지 못할경우 -1을 리턴한다.

삼성 A형 기출문제다 문제가 참 더럽다고 생각한다.

두번째 도전이라 생각보다 시간이 덜 걸렸고 맨처음엔 풀다가 포기했었다.

문제를 풀 순서는 머릿속에 있었지만 간선을 찾지 못했었고, 최소신장트리 알고리즘 또한 아직 익숙지 않았었다.

최소신장트리를 공부하였고 위 문제에 적용하여 해결하였다.

Code

언어 : JAVA

메모리 : 14,396 kb

실행시간 : 108 ms

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, count;
    static int[][] map;
    static int[][] graph;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    static int[] dist;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int tmp = sc.nextInt();
                if (tmp == 1)
                    map[i][j] = -1;
                else
                    map[i][j] = tmp;
            }
        }
        //1. 섬을 분리한다.
        count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == -1)
                    BFS(i, j, ++count);
            }
        }
        //2. 그래프를 생성한다.
        graph = new int[count][count];

        for (int i = 0; i < count; i++) {
            for (int j = 0; j < count; j++) {
                if (i == j)
                    continue;
                graph[i][j] = Integer.MAX_VALUE;
            }
        }
        //3. 생성된 그래프의 간선을 연결한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {

                if (map[i][j] != 0) {
                    for (int dir = 0; dir < 4; dir++) {
                        int r = i + dr[dir];
                        int c = j + dc[dir];
                        if (range(r, c)) {
                            if (map[r][c] == 0) {
                                makeGraph(new int[] { i, j }, new int[] { r, c }, dir, 1);
                            }
                        }
                    }
                }
            }
        }

        dist = new int[count];
        System.out.println(prim(graph));

    }

    public static int prim(int[][] graph) {
        Arrays.fill(dist, -1);
        dist[0] = 0;

        for (int k = 0; k < count; k++) {
            int minWeight = Integer.MAX_VALUE;
            int minVertex = 0;

            for (int i = 0; i < count; i++) {
                if (dist[i] < 0)
                    continue;
                for (int j = 0; j < count; j++) {
                    if (dist[j] >= 0)
                        continue;
                    if (minWeight > graph[i][j]) {
                        minWeight = graph[i][j];
                        minVertex = j;
                    }
                }
            }
            dist[minVertex] = minWeight;

        }
        int sum = 0;
        for (int i = 1; i < count; i++) {
            if(dist[i]==-1)
                return -1;
            sum += dist[i];
        }
        return sum;
    }

    private static void makeGraph(int[] start, int[] cur, int dir, int cnt) {
        int r = cur[0] + dr[dir];
        int c = cur[1] + dc[dir];
        if (range(r, c)) {
            if (map[r][c] == 0) {
                makeGraph(start, new int[] { r, c }, dir, ++cnt);
            } else {
                int s = map[start[0]][start[1]] - 1;
                int e = map[r][c] - 1;
                if (cnt >= 2) {
                    if (graph[s][e] > cnt) {
                        graph[s][e] = cnt;
                        graph[e][s] = cnt;
                    }
                }
            }
        }
    }

    private static void BFS(int i, int j, int cnt) {
        Queue<int[]> q = new LinkedList<int[]>();
        q.offer(new int[] { i, j, cnt });
        map[i][j] = cnt;

        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)) {
                    if (map[r][c] == -1) {
                        q.offer(new int[] { r, c, cnt });
                        map[r][c] = cnt;
                    }
                }
            }
        }
    }
    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < M)
            return true;
        return false;
    }
}

[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;
    }
}

[BOJ] 4963. 섬의 개수 - DFS

제출일 : 2019-10-07

문제 풀이 시간 : 10M

난이도 : ★

Problem

link : https://www.acmicpc.net/problem/4963

Input

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

Output

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

Example

input

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

output

0
1
1
3
1
9

Solution & Inpression

DFS의 가장 기본적인 문제

Code

언어 : JAVA

메모리 : 33,252 kb

실행시간 : 312 ms

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

public class Main_백준_4963_섬의개수_DFS {
    static int W, H;
    static int[][] map;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (true) {
            W = sc.nextInt();
            H = sc.nextInt();

            if (W == 0 && H == 0)
                break;

            map = new int[H][W];

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    int tmp = sc.nextInt();
                    if (tmp == 1)
                        map[i][j] = -1;
                    else
                        map[i][j] = tmp;
                }
            }

            int cnt = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == -1) {
                        map[i][j] = ++cnt;
                        solve(i, j, cnt);
                    }
                }
            }
            System.out.println(cnt);

            // for (int[] is : map)
            // System.out.println(Arrays.toString(is));

        } // end of tc
        sc.close();
    }// end of main

    private static void solve(int i, int j, int cnt) {
        int[] dr = { -1, 1, 0, 0, 1, 1, -1, -1 };
        int[] dc = { 0, 0, -1, 1, 1, -1, -1, 1 };

        for (int k = 0; k < 8; k++) {
            int r = i + dr[k];
            int c = j + dc[k];
            if (range(r, c)) {
                if (map[r][c] == -1) {
                    map[r][c] = cnt;
                    solve(r, c, cnt);
                }
            }
        }
    }

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

[BOJ] 4963. 섬의 개수 - BFS

제출일 : 2019-10-07

문제 풀이 시간 : 30M

난이도 : ★★☆

Problem

link : https://www.acmicpc.net/problem/4963

Input

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

Output

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

Example

input

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

output

0
1
1
3
1
9

Solution & Inpression

1차 시도 : 메모리 초과

    private static void solve(int i, int j, int cnt) {
        int[] dr = { -1, 1, 0, 0, 1, 1, -1, -1 };
        int[] dc = { 0, 0, -1, 1, 1, -1, -1, 1 };

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { i, j });

        while (!q.isEmpty()) {
            int[] tmp = q.poll();
            map[tmp[0]][tmp[1]] = cnt;

            for (int k = 0; k < 8; k++) {
                int r = tmp[0] + dr[k];
                int c = tmp[1] + dc[k];
                if (range(r, c)) {
                    if (map[r][c] == -1) {
                        q.offer(new int[] { r, c });
                    }
                }
            }
        }
    }

방문처리를 큐에서 값을 빼올때 처리하였다.

이렇게 작성하였다면 이미 큐에 담겨있지만 방문이 안되었다 판단하기 때문에 불필요하게 큐에 값이 들어가게 되는 현상이 발생하여 메모리초과가 발생한다.

방문처리를 아래와 같은 방법으로 수정하여 메모리 초과는 발생하지 않았다.

Code

언어 : JAVA

메모리 : 32,984 kb

실행시간 : 328 ms

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

public class Main_백준_4963_섬의개수 {
    static int W, H;
    static int[][] map;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (true) {
            W = sc.nextInt();
            H = sc.nextInt();

            if (W == 0 && H == 0)
                break;

            map = new int[H][W];

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    int tmp = sc.nextInt();
                    if (tmp == 1)
                        map[i][j] = -1;
                    else
                        map[i][j] = tmp;
                }
            }

            int cnt = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == -1) {
                        solve(i, j, ++cnt);
                    }
                }
            }
            System.out.println(cnt);

            // for(int[] is : map)
            // System.out.println(Arrays.toString(is));

        } // end of tc
        sc.close();
    }// end of main

    private static void solve(int i, int j, int cnt) {
        int[] dr = { -1, 1, 0, 0, 1, 1, -1, -1 };
        int[] dc = { 0, 0, -1, 1, 1, -1, -1, 1 };

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { i, j });
        map[i][j] = cnt;

        while (!q.isEmpty()) {
            int[] tmp = q.poll();

            for (int k = 0; k < 8; k++) {
                int r = tmp[0] + dr[k];
                int c = tmp[1] + dc[k];
                if (range(r, c)) {
                    if (map[r][c] == -1) {
                        q.offer(new int[] { r, c });
                        map[r][c] = cnt;
                    }
                }
            }
        }
    }

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

[SWEA] 4301. 콩 많이 심기 D4 - Simulation

제출일 : 2019-09-24

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWLv-yZah48DFAVV

Input

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

각 테스트 케이스는 한 줄로 이루어져 있으며, 가로길이 N, 세로길이 M이 주어진다.

(1 ≤ N, M ≤ 1000)

Output

각 테스트 케이스마다 밭에 놓을 수 있는 콩의 최대 개수를 출력하라.

Example

input

1
3 2

output

#1 4    

Solution & Inpression

해당 위치에서 콩을 심을 수 있는지 검사한뒤 콩을 심을 수 있다면 콩을 콩을 심는다.

Code

언어 : JAVA

메모리 : 94,668 kb

실행시간 : 279 ms

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

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

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

        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            // 가로길이 N, 세로길이 M (1 ≤ N, M ≤ 1000)
            N = sc.nextInt();
            M = sc.nextInt();

            map = new int[M][N];
            cnt = 0;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    solve(i, j);
                }
            }
            System.out.println("#"+tc+" "+cnt);
        }
        sc.close(); // Scanner close
    }

    private static void solve(int i, int j) {

        int[] dx = { -2, 2, 0, 0 };
        int[] dy = { 0, 0, -2, 2 };

        boolean flag = true;

        for (int k = 0; k < 4; k++) {
            int nx = i + dx[k];
            int ny = j + dy[k];

            if (range(nx, ny)) { // 범위 안이고
                if (map[nx][ny] == 1) { // 콩이 심어져 있으면
                    flag = false; // 콩 못심어
                    break;
                }
            }
        }

        if (flag) {
            // System.out.println("i = "+i+", j= "+j);

            map[i][j] = 1;//콩심고
            cnt++; //카운트
        }

    }

    static boolean range(int x, int y) {
        if (0 <= x && x < M && 0 <= y && y < N)
            return true;
        return false;
    }
}

[SWEA] 4796. 의석이의 우뚝 선 산 D4 - Simulation

제출일 : 2019-09-24

문제 풀이 시간 : 1H

난이도 : ★★☆

Problem

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

Input

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

각 테스트 케이스의 첫 번째 줄에는 자연수 N(3≤N≤50,000)이 주어진다.

다음 줄에는 N개의 자연수 h1,…,hN (1≤hi≤10^9)이 순서대로 공백 하나로 구분되어 주어진다.

모든 1≤i＜j≤N 에 대해 hi≠hj 이다.

Output

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 우뚝 선 산이 될 수 있는 구간의 개수를 출력하라.

Example

input

3
3
1 3 2
3
3 2 1
9
1 4 6 5 3 7 9 2 8

output

#1 1
#2 0
#3 6    

Solution & Inpression

1 2 5 3 2 1

위와 같은 경우 우뚝 선 산이 될수 있는 구간은

1 2 5 3

1 2 5 3 2

1 2 5 3 2 1

2 5 3

2 5 3 2

2 5 3 2 1

총 6가지 = 2 X 3 으로 구할수 있다.

Code

언어 : JAVA

메모리 : 102,944 kb

실행시간 : 1,584 ms

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

public class Solution {
    static int N;

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

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

            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = sc.nextInt();
            }

            for (int i = 0; i < N - 2; i++) {
                int idx = i; 
                int tmp1 = 0;

                while (arr[idx] < arr[++idx]) {
                    tmp1++;
                    if (!range(idx + 1)) {
                        idx++;
                        break;
                    }
                }
                idx--;

                if (i == idx || idx == (N - 1))
                    continue;

                i = idx - 1;

                int tmp2 = 0;
                while (arr[idx] > arr[++idx]) {
                    tmp2++;
                    if (!range(idx + 1)) {
                        idx++;
                        break;
                    }
                }
                idx--;
                cnt += tmp1 * tmp2;
            }
            System.out.println("#" + tc + " " + cnt);
        }
        sc.close(); // Scanner close
    }

    static boolean range(int x) {
        if (0 <= x && x < N)
            return true;
        return false;
    }
}

[JUNGOL] 1841. 월드컵 - DFS

제출일 : 2019-10-01

문제 풀이 시간 : 1H 45M

난이도 : ★★★☆

Problem

link : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1114&sca=50&stx=%EC%9B%94%EB%93%9C%EC%BB%B5

Input

첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다.

Output

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

Example

input

5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4 
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3 
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4

output

1 1 0 0

Solution & Inpression

결과적으론 BFS를 이용하면 된다.

하지만 나는 단순하게 조건을 주어 해결하려 하였다. 하지만 계속 예외가 발생했고 생각하지 못한 조건들이 계속 발견되어 총 라인수가 150라인을 넘어가고있었다.

다시 생각을 하였다.

전체 경기는 총 15번 진행된다

A vs B C D E F
B vs C D E F
C vs D E F
D vs E F
E vs F

또한 각 경기는 3가지 경우가 존재한다

• Team1 승리 , Team2 패배
• Team1 비김 , Team2 비김
• Team1 패배 , Team2 승리

이때 시간복잡도는 O(3^15) 로 완전탐색을 진행할 수 있다.

따라서 완전탐색을 이용하여 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 16 mb

실행시간 : 1009 ms

import java.util.Scanner;

public class Main {

    static int[] team1 = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 };
    static int[] team2 = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 };
    static int[][] matrix;
    static int[][] result;
    static int[] ans;

    static void dfs(int tc, int game) {
        if (game == 15) { // 모든 경기를 마치고
            if (ans[tc] != 1) { // 이전에 판별되지 않았다면
                // 판별시작
                for (int i = 0; i < 6; i++) {
                    for (int j = 0; j < 3; j++)
                        // 결과가 하나라도 같지 않다면
                        if (matrix[i][j] != result[i][j])
                            return;
                }

                // 경기결과가 일치한다면
                ans[tc] = 1; // 결과테이블에 저장
                return;

            } else
                return;
        }

        // ---------------------DFS--------------------- //
        // |승0|무1|패2|

        int t1 = team1[game];
        int t2 = team2[game];

       // t1 win, t2 lose
        result[t1][0]++;        result[t2][2]++;
        dfs(tc, game + 1);
        result[t1][0]--;        result[t2][2]--;

        // t1 draw, t2 draw
        result[t1][1]++;        result[t2][1]++;
        dfs(tc, game + 1);
        result[t1][1]--;        result[t2][1]--;

        // t1 lose, t2 win
        result[t1][2]++;        result[t2][0]++;
        dfs(tc, game + 1);
        result[t1][2]--;        result[t2][0]--;

    }

    public static void main(String[] args) {
        // 백준_6987_월드컵
        // 정올_1841_월드컵
        Scanner sc = new Scanner(System.in);

        matrix = new int[6][3];
        result = new int[6][3];
        ans = new int[4];

        for (int tc = 0; tc < 4; tc++) {
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 3; j++) {
                    matrix[i][j] = sc.nextInt();
                }
            }
            dfs(tc, 0);
        }

        for (int x : ans)
            System.out.print(x + " ");
        System.out.println();

        sc.close();
    }
}