반응형

* 핵심

Backtracking으로 문제 접근, 계산 전에 연산자의 수를 하나 뺏다가 다시 추가하는 작업 필수


* 문제

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

  • 1+2+3-4×5÷6
  • 1÷2+3+4-5×6
  • 1+2÷3×4-5+6
  • 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

  • 1+2+3-4×5÷6 = 1
  • 1÷2+3+4-5×6 = 12
  • 1+2÷3×4-5+6 = 5
  • 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 최댓값과 최솟값은 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 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
47
48
import java.io.*;
import java.util.*;
 
public class Main {
    public static int n;
    public static int[] num;
    public static int[] op = new int[4];
    public static int min = 1000000000;
    public static int max = -1000000000;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(stk.nextToken());
        num = new int[n];
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(stk.nextToken());
        }
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            op[i] = Integer.parseInt(stk.nextToken());
        }
        backtracking(num[0], 1);
        System.out.println(max);
        System.out.println(min);
    }
 
    public static void backtracking(int res, int cnt) {
        if (cnt == n) {
            min = Math.min(min, res);
            max = Math.max(max, res);
            return;
        } else {
            for (int i = 0; i < 4; i++) {
                if (op[i] != 0) {
                    op[i]--;        //해당 연산자 개수 하나 감소
                    if (i == 0) backtracking(res + num[cnt], cnt + 1);
                    if (i == 1) backtracking(res - num[cnt], cnt + 1);
                    if (i == 2) backtracking(res * num[cnt], cnt + 1);
                    if (i == 3) backtracking(res / num[cnt], cnt + 1);
                    op[i]++;        //해당 연산자 개수 
                }
            }
        }
    }
}
cs


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

'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글

[Algorithm] 백준/16236 :: 아기 상어  (0) 2019.03.10
[Algorithm] 백준/14502 :: 연구소  (0) 2019.03.02
[Algorithm] 백준/14501 :: 퇴사  (0) 2019.02.12
[Algorithm] 백준/14889 :: 스타트와 링크  (0) 2019.01.04
반응형

* 핵심

알파벳 개수만큼 26개의 boolean 배열을 만들고 BackTracking으로 경로 확인


* 문제

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R,C<=20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.


* 소스 코드

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
import java.io.*;
import java.util.*;
 
public class Main {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int[][] map;
    public static int ans = 0;
    public static boolean[] visited = new boolean[26];
    static int r;
    static int c;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        r = Integer.parseInt(stk.nextToken());
        c = Integer.parseInt(stk.nextToken());
        map = new int[r][c];
 
        for (int i = 0; i < r; i++) {
            String s = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = s.charAt(j) - 'A';
            }
        }
 
        bt(0, 0, 0);
        System.out.println(ans);
    }
 
    public static void bt(int x, int y, int depth) {
        if (visited[map[x][y]]) {
            ans = Math.max(ans, depth);
            return;
        } else {
            visited[map[x][y]] = true;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                    bt(nx, ny, depth + 1);
                }
            }
            visited[map[x][y]] = false;        //방문여부 초기화
        }
    }
}
cs


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

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

[Algorithm] 백준/1629 :: 곱셈  (0) 2019.01.08
[Algorithm] 백준/2661 :: 좋은수열  (0) 2019.01.04
[Algorithm] 백준/2583 :: 영역 구하기  (0) 2018.12.31
[Algorithm] 백준/7576 :: 토마토  (0) 2018.12.30
반응형

* BackTracking

왔던 길을 되추척하는 방법


BackTracking 과 DFS는 비슷하지만 다른 차이점이 있다.

DFS 의 경우 방문한 점을 다시 방문하지 않는다는 특징이 있지만,

BackTracking 의 경우는 방문한 점을 다시 방문할 수 있다.

>> DFS는 순서의 상관 없이 M개중에서 N개를 뽑을 때 사용

>> BackTracking은 M개 중에서 N개를 순서에 따라 뽑을 때 사용



* BackTracking 시간 복잡도 

BackTracking 의 시간 복잡도는 O(2^n) 이다.

N의 범위가 보통 26 이하인 경우 사용 가능하다.


* BackTracking 유의할 점

DFS와 다르게 방문한 점을 다시 방문할 수 있기 때문에, 방문 이후 boolean visied 값을 초기화작업 필수


* BackTracking 작동 방식

Ex) 4개의 선택지가 있고, 선택시 1, 미선택시 0이라고 가정할 때, 작동 순서는 다음과 같다.

0

0 

0 

0 

0

0 

0 

1 

0

0 

1 

0 

0

0 

1 

1 


마지막 선택지의 경우 이미 다녀온 경우에도 불구하고 앞에 선택지가 변경되면 마지막 선택지를 다시 방문해야 한다.

BackTracking 의 경우 위와 같은 방식으로 진행된다.

이를 Tree 구조로 나타내면 다음과 같다.


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

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

[Algorithm Tech] Divide and Conquer(분할 정복)  (0) 2019.01.08
[Algorithm Tech] Bitmask(비트마스크)  (0) 2019.01.08
[Algorithm Tech] BFS vs DFS  (0) 2018.12.29
[Algorithm Tech] 알고리즘 기본 지식  (0) 2018.12.27
반응형

* 핵심

BFS 를 이용하기 위해 Static Class와 Static Method 사용


* 문제

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.


* 소스 코드

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
80
81
82
import java.io.*;
import java.util.*;
 
public class Main {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int m = 0;
    static int n = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        m = Integer.parseInt(stk.nextToken());
        n = Integer.parseInt(stk.nextToken());
        int k = Integer.parseInt(stk.nextToken());
 
        int[][] map = new int[m][n];
        boolean[][] visited = new boolean[m][n];
 
        for (int i = 0; i < k; i++) {
            stk = new StringTokenizer(br.readLine());
            int y1 = Integer.parseInt(stk.nextToken());
            int x1 = Integer.parseInt(stk.nextToken());
            int y2 = Integer.parseInt(stk.nextToken());
            int x2 = Integer.parseInt(stk.nextToken());
            square(m-x1, y1, m-x2, y2, map);    //map에 입력받는 직사각형 저장
        }
 
        ArrayList<Integer> alist = new ArrayList<>();
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 0 && !visited[i][j]){
                    Queue<pair> q = new LinkedList<>();
                    q.add(new pair(i, j));
                    int cnt = 0;    //각 BFS 넓이
                    while (!q.isEmpty()){
                        pair p = q.poll();
                        if (!visited[p.x][p.y] && map[p.x][p.y] == 0){
                            cnt++;
                            visited[p.x][p.y] = true;
                            for (int l = 0; l < 4; l++) {
                                int nx = p.x + dx[l];
                                int ny = p.y + dy[l];
                                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && map[nx][ny] == 0){
                                    q.add(new pair(nx, ny));
                                }
                            }
                        }
                    }
                    alist.add(cnt);
                }
            }
        }
        Collections.sort(alist);
        sb.append(alist.size()).append("\n");
        for (int i = 0; i < alist.size(); i++) {
            sb.append(alist.get(i)).append("\n");
        }
        System.out.println(sb);
    } // End of Main
 
    public static void square(int x1, int y1, int x2, int y2, int[][] map){
        for (int i = x2; i < x1; i++) {
            for (int j = y1; j < y2; j++) {
                if (map[i][j] != 1)
                    map[i][j] = 1;
            }
        }
    }
 
    public static class pair {    //Queue에 저장될 Static Class
        int x, y;
 
        public pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
cs


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

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

[Algorithm] 백준/2661 :: 좋은수열  (0) 2019.01.04
[Algorithm] 백준/1987 :: 알파벳  (0) 2019.01.04
[Algorithm] 백준/7576 :: 토마토  (0) 2018.12.30
[Algorithm] 백준/11724 :: 연결 요소의 개수  (0) 2018.12.29
반응형

* 핵심

BFS를 이용하여 좌표 확인하기


* 문제

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N 은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 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
44
45
46
47
48
49
50
51
52
53
54
55
56
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 m = Integer.parseInt(stk.nextToken());
        int n = Integer.parseInt(stk.nextToken());
        int[][] map = new int[n][m];
        int check = 0;
        Queue<pair> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] != -1) check++;
                if (map[i][j] == 1) q.add(new pair(i, j, 0));
            }
        }
 
        boolean[][] visited = new boolean[n][m];
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int ans = 0;
        int check2 = 0;
        while (!q.isEmpty()) {
            pair p = q.poll();
            if (!visited[p.i][p.j]) {
                check2++;
                visited[p.i][p.j] = true;
                ans = Math.max(ans, p.w);
                for (int i = 0; i < 4; i++) {
                    int nx = p.i + dx[i];
                    int ny = p.j + dy[i];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] != -1) {
                        q.add(new pair(nx, ny, p.w + 1));
                    }
                }
            }
        }
        if (check != check2) System.out.println("-1");
        else System.out.println(ans);
    } // End of Main
 
    public static class pair {
        int i, j, w;
 
        public pair(int i, int j, int w) {
            this.i = i;
            this.j = j;
            this.w = w;     //Depth
        }
    }
}
cs



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

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

[Algorithm] 백준/1987 :: 알파벳  (0) 2019.01.04
[Algorithm] 백준/2583 :: 영역 구하기  (0) 2018.12.31
[Algorithm] 백준/11724 :: 연결 요소의 개수  (0) 2018.12.29
[Algorithm] 백준/1181 :: 단어 정렬  (0) 2018.12.29
반응형

* 핵심

BFS or DFS를 이용하여 끊어진 갯수 구하기


* 문제

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.


* 소스코드(BFS & DFS)

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
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 m = Integer.parseInt(stk.nextToken());
 
        boolean[] visited = new boolean[n+1];
        ArrayList<Integer>[] edge = new ArrayList[n+1];
        for (int i = 0; i < n+1; i++) {
            edge[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());
 
            edge[u].add(v);
            edge[v].add(u);
        }
        int ans = 0;
        for (int i = 1; i < m+1; i++) {
            //BFS
            if (!visited[i]){
                ans++;
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                while (!q.isEmpty()){
                    int tmp = q.poll();
                    if (!visited[tmp]) {
                        visited[tmp] = true;
                        for (int j = 0; j < edge[i].size(); j++) {
                            q.add(edge[tmp].get(j));
                        }
                    }
                }
            }
 
            //DFS
            if (!visited[i]){
                ans++;
                dfs(i, edge, visited);
            }
        }
        System.out.println(ans);
    }
 
    //DFS
    public static void dfs(int v, ArrayList<Integer>[] edge, boolean[] visited){
        if (!visited[v]){
            visited[v] = true;
            for (int i = 0; i < edge[v].size(); i++) {
                dfs(edge[v].get(i), edge, visited);
            }
        }
    }
}
cs


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

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

[Algorithm] 백준/2583 :: 영역 구하기  (0) 2018.12.31
[Algorithm] 백준/7576 :: 토마토  (0) 2018.12.30
[Algorithm] 백준/1181 :: 단어 정렬  (0) 2018.12.29
[Algorithm] 백준/14698 :: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)  (0) 2018.12.28
반응형

* 너비 우선 탐색(BFS, Breadth-First Search)

  • 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
  • Queue로 구현
  • 간선에 가중치가 없는 그래프에서는 방문하는 depth가 최단거리가 된다
  • 주로 격자판, 최단거리 구할 때 사용
  • while (!q.isEmpty()) -> if (!visited[q.poll()]) -> q.add 순서의 메소드 진행


* 깊이 우선 탐색(DFS, Depth-First Search)

  • 재귀로 구현(코드가 간단)
  • 자식 노드의 수를 파악하기 편리
  • 주로 Tree에서 사용
  • dfs 재귀함수에 탈출조건과 재귀내용 작성


* 주요개념

ArrayList의 배열로 구현이 필요

정점의 개수(N)만큼 ArrayList 배열을 만들고, M개의 간선을 N번째 index에 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
ArrayList<Integer>[] edge = new ArrayList[n+1];
for (int i = 0; i <= n; i++) {
    edge[i] = new ArrayList<>();
}   //ArrayList 추가
 
for (int i = 0; i < m; i++) {
    stk = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(stk.nextToken());
    int v = Integer.parseInt(stk.nextToken());
 
    edge[u].add(v);        // u 정점에 v로 가는 간선 추가
    edge[v].add(u);        // v 정점에 u로 가는 간선 추가
}
cs


* 소스 코드(백준 1260번 DFS와 BFS)

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static ArrayList<Integer> alist = new ArrayList<>();
 
    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 m = Integer.parseInt(stk.nextToken());
        int vv = Integer.parseInt(stk.nextToken());
 
        ArrayList<Integer>[] edge = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            edge[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());
            edge[u].add(v);
            edge[v].add(u);
        }
 
        for (int i = 0; i < edge.length; i++) {
            Collections.sort(edge[i]);
        }
 
        //DFS
        dfs(vv, edge, new boolean[n+1]);
        System.out.println();
 
        //BFS
        alist = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> q = new LinkedList<>();
        q.add(vv);
        while (!q.isEmpty()) {
            int tmp = q.poll();
            if (!visited[tmp]) {
                visited[tmp] = true;
                System.out.print(tmp + " ");
                for (int i = 0; i < edge[tmp].size(); i++) {
                    q.add(edge[tmp].get(i));
                }
            }
        }
    }
 
    //DFS
    public static void dfs(int v, ArrayList<Integer>[] edge, boolean[] visited) {
        if (!visited[v]) {
            alist.add(v);
            visited[v] = true;
            System.out.print(v + " ");
            for (int i = 0; i < edge[v].size(); i++) {
                dfs(edge[v].get(i), edge, visited);
            }
        }
    }
}
cs


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

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

[Algorithm Tech] Bitmask(비트마스크)  (0) 2019.01.08
[Algorithm Tech] BackTracking  (0) 2019.01.03
[Algorithm Tech] 알고리즘 기본 지식  (0) 2018.12.27
[Algorithm Tech] Stack & Queue & PriorityQueue  (0) 2018.12.13
반응형

* 핵심

Comparator 사용하여 조건 만족


* 문제

*개념

Comparator 를 이용하여 길이가 짧은 것부터, 같으면 사전순으로 정렬한다.


* 소스코드

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
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));
        StringBuilder sb = new StringBuilder();
 
        int n = Integer.parseInt(br.readLine());
        HashSet hs = new HashSet();     //중복 제거
        ArrayList<String> alist = new ArrayList<>();
        while (n-->0) {
            String s = br.readLine();
            if (!hs.contains(s)) {
                hs.add(s);
                alist.add(s);
            }
        }
        alist.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() == o2.length()) return o1.compareTo(o2);    //사전순
                else return Integer.compare(o1.length(), o2.length());      //길이 오름차순
            }
        });
        for (int i = 0; i < alist.size(); i++) {
            sb.append(alist.get(i)).append("\n");
        }
        System.out.println(sb);
    }   //End of Main
}
cs


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

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

[Algorithm] 백준/7576 :: 토마토  (0) 2018.12.30
[Algorithm] 백준/11724 :: 연결 요소의 개수  (0) 2018.12.29
[Algorithm] 백준/14698 :: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)  (0) 2018.12.28
[Algorithm] 백준/1620 :: 나는야 포켓몬 마스터 이다솜  (0) 2018.12.27

티스토리툴바