반응형

자료구조....,,, 정렬.....,,


나는 해쉬맵 자료구조를 사용했다.

범위가 (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 이므로 counting sort가 불가능하다.

그래서 해쉬맵을 사용했다. 그리고 해쉬맵의 키값들을 리스트에 저장해줘서 정렬 후 출력했다.


풀이

1. 해쉬맵에 키와 빈도수를 저장한다.

2. 해쉬맵에 저장된 모든 키들을 리스트에 저장한다.

3. 리스트들안에 저장된 키들을 빈도에 따라서 정렬한다.

4. 출력


소스

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
 
import java.util.Comparator;
 
public class Main {
 
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
 
        int N = Integer.parseInt(str[0]);
        
        str = br.readLine().split(" ");
        HashMap<Integer, Integer> list = new LinkedHashMap<Integer, Integer>();
        
        //해쉬맵을 이용
        for (int i = 0; i < N; i++) {
            // 키가 존재하면 value를 +1
            if (list.containsKey(Integer.parseInt(str[i]))) {
                list.replace(Integer.parseInt(str[i]), list.get(Integer.parseInt(str[i])) + 1);
            }
            // 키가 없을시 value 값을 1로 생성한다.
            else {
                list.put(Integer.parseInt(str[i]), 1);
            }
        }
        //key들을 모두 배열에 저장한다.
        ArrayList<Integer> v = new ArrayList<Integer>(list.keySet());
 
        //배열에 저장된 키들의 값을 value값으로 내림차순 정렬한다.
        Collections.sort(v, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                //list.get(b) 와 list.get(a)의 위치가 바뀌면 오름차순이 된다.
                return Integer.compare(list.get(b), list.get(a));
            }
        });
        //Iterator를 통해서 출력한다.
        Iterator<Integer> it = v.iterator();
        while (it.hasNext()) {
            Integer element = it.next();
            for(int i=0; i<list.get(element); i++){
                System.out.print(element+" ");    
            }
            
        }
    }
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1049 - 기타줄 (자바)  (0) 2018.02.20
[BOJ] 백준 2156 - 포도주 시식 (자바)  (0) 2018.02.20
[BOJ] 백준 7576 - 토마토 (자바)  (0) 2018.02.20
[BOJ] 백준 14503 - 로봇청소기 (자바)  (0) 2018.02.20
[BOJ] 백준 5555 - 반지 (자바)  (0) 2018.02.15
반응형

BFS,,...


오랜만에 BFS 문제 풀려고 했었는데 생각이 않났다. 그래서 시간 두고 다시 풀어봄.

아주 단순히 이전 값에 +1 해주면 되는 거였다.


풀이

1. 토마토가 익은 점들을 큐에 넣어준다. (동시 다발적으로 일어나기 때문에 큐를 사용한 BFS)

2. 익은 토마토 상하좌우를 탐색하며 익지 않은 토마토가 있으면 그 위치를 큐에 넣어준다. (그 위치의 값은 최대 일수를 계산하기 위해 전 위치 +1 을 해준다.)

3. 큐가 빌때까지 계속해준다.

4. 전체 토마토들을 탐색하여  익지않은 토마토(0 값) 하나라도 있으면 -1를 출력한다. 

5. 그 외는 최대 일수를 출력한다.


소스

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int M = Integer.parseInt(str[0]);
        int N = Integer.parseInt(str[1]);
 
        int[][] arr = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
 
            }
        }
        //----------------- 입력 부 ------------------
        BFS(arr, N, M);
    }
 
    public static void BFS(int[][] arr, int N, int M) {
        Queue<DOT> q = new LinkedList<DOT>();
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 1)
                    //익은 토마토가 있는 모든 위치를 큐에 담는다.
                    q.add(new DOT(i, j));
            }
        }
 
        while (!q.isEmpty()) {
            //익은 토마토의 상하좌우는 다음에 익기 때문에 큐에 담아야한다.
            DOT dot = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = dot.x + dx[i];
                int nextY = dot.y + dy[i];
 
                //범위 밖 패스
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                //다음 위치가 익지 않은 토마토가 아니면 패스
                if (arr[nextX][nextY] != 0) {
                    continue;
                }
                //최대 일수를 구하기 때문에 1로 바꾸는 것이 아니라 현재 일수 +1 을 해줘야한다.
                arr[nextX][nextY] = arr[dot.x][dot.y] + 1;
                q.add(new DOT(nextX, nextY));
            }
            //print(arr, N, M); // 농장 전체 출력
            //System.out.println();
        }
        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) {
                    //토마토가 모두 익지 못한 상황이라면 -1 을 출력한다.
                    System.out.println(-1);
                    return;
                }
                max = Math.max(max, arr[i][j]);
            }
        }
        //그렇지 않다면 최대값을 출력한다.
        System.out.println(max - 1);
 
    }
    //농장을 전체 보여주는 함수
    public static void print(int[][] arr, int N, int M) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}
 
class DOT {
    int x;
    int y;
 
    DOT(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 2156 - 포도주 시식 (자바)  (0) 2018.02.20
[BOJ] 백준 2910 - 빈도 정렬 (자바)  (0) 2018.02.20
[BOJ] 백준 14503 - 로봇청소기 (자바)  (0) 2018.02.20
[BOJ] 백준 5555 - 반지 (자바)  (0) 2018.02.15
[BOJ] 백준 11047 - 동전 0 (자바)  (0) 2018.02.13
반응형

삼성 SW 역량테스트,,,,,,


17년 상반기 DS부문 1번문제 였다.

맨 처음에는 그냥 if, while, for 등의 떡칠로 문제를 풀게 되었다.

2번째 풀 때는 반복문으로 풀면 조금 더 쉽지 않을까? 싶어서 Queue를 이용해서 풀었는데

다음 x,y좌표 구하는 규칙은 쉽게 구할 수 있었지만 방향을 구하는 규칙을 찾는데 너무 많은 시간을 투자했다.

결국 맨 처음 조건문,반복문 떡칠이 시간이 훨씬 조금 걸렸다.... 아무튼 풀긴 풀었다.


1. 현재 위치를 청소한다.

 --> 현재 위치 청소

2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 

 --> 위치는 제자리, 방향만 왼쪽으로 회전

  2-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

    --> 왼쪽으로 회전한 방향의 앞이 청소되지 않았다면 한칸 전진한 후 1번으로 진행한다. (즉 앞의 칸 청소부터 다시 시작한다)

  2-2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

    --> 왼쪽으로 회전한 방향의 앞이 청소할 공간이 없다면, 다시 왼쪽으로 회전한다.

  2-3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

    --> 한바퀴를 다 돌았을 때 (네방향 모두 청소가 되어있을 때) 앞이 벽이라면, 뒤로 한칸 이동한다.

    --> 처음 바라보는 방향이 북쪽일 경우 탐색은 서쪽, 남쪽, 동쪽, 북쪽 순이 된다. 결국 마지막에 바라보는 방향은 북쪽이다. 그럴경우 남쪽으로 후진한다.

  2-4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

     --> 말 그대로...

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.


로봇청소기의 동작과정이다. 저 문제를 이해하는게 엄청 어렵다. 내가 설명을 잘 했는지도 잘 모르겠다.

문제만 잘 이해한다면 쉽게 풀 수 있는 문제이다. 풀이도 딱히 필요없다. 


풀이

풀이는 이동과정으로 대체 한다.


소스 - 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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    static int seo = 3;
    static int dong = 1;
    static int nam = 2;
    static int buk = 0;
 
    public static void main(String[] args) throws Exception {
 
        //Scanner sc = new Scanner(new FileInputStream("input.txt"));
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
 
        int r = sc.nextInt()+1;
        int c = sc.nextInt()+1;
        int d = sc.nextInt();
 
        int[][] arr = new int[N + 2][M + 2];
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        int cnt = 0;
        int result = 0;
        while (r > 0 && c > 0 && r <= N && c <= M) {
            arr[r][c] = -1;
            // System.out.println(r + " " + c + " " + d);
            // sc1.nextLine();
            if (cnt == 4) {
                if (d == dong) {
                    if (arr[r][c - 1] == 1) {
                        break;
                    }
                    c--;
 
                } else if (d == seo) {
                    if (arr[r][c + 1] == 1) {
                        break;
                    }
                    c++;
                }
 
                else if (d == nam) {
                    if (arr[r - 1][c] == 1) {
                        break;
                    }
                    r--;
                } else if (d == buk) {
                    if (arr[r + 1][c] == 1) {
                        break;
                    }
                    r++;
                }
                cnt = 0;
            }
 
            else {
                if (d == dong) {
                    if (arr[r - 1][c] == 0) {
                        cnt = 0;
                        r--;
                        result++;
                    } else {
                        cnt++;
                    }
                    d = buk;
 
                } else if (d == seo) {
                    if (arr[r + 1][c] == 0) {
                        cnt = 0;
 
                        r++;
                        result++;
                    } else {
                        cnt++;
                    }
                    d = nam;
 
                }
 
                else if (d == nam) {
                    if (arr[r][c + 1] == 0) {
                        cnt = 0;
 
                        c++;
                        result++;
                    } else {
                        cnt++;
                    }
                    d = dong;
 
                } else if (d == buk) {
                    if (arr[r][c - 1] == 0) {
                        cnt = 0;
 
                        c--;
                        result++;
                    } else {
                        cnt++;
                    }
                    d = seo;
 
                }
            }
        }
        result = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                //System.out.print(arr[i][j] + "\t");
                if (arr[i][j] == -1) {
                    result++;
                }
            }
            //System.out.println();
 
        }
        System.out.println(result);
    }
}
cs


소스 - 2 (규칙으로)

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int N;
    static int M;
    static int count = 0;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
 
        String[] str = br.readLine().split(" ");
 
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        str = br.readLine().split(" ");
        int start_x = Integer.parseInt(str[0]);
        int start_y = Integer.parseInt(str[1]);
        int start_dir = Integer.parseInt(str[2]);
 
        int[][] arr = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        //--------------입력--------------
        
        Search(arr, start_x, start_y, start_dir);    //청소 실행 함수
        Check(arr);    //청소한 칸의 개수를 구함
        System.out.println(count);
    }
 
    public static void Search(int[][] arr, int start_x, int start_y, int start_dir) {
        Queue<Dot> q = new LinkedList<Dot>();
        arr[start_x][start_y] = 9;
        q.add(new Dot(start_x, start_y, start_dir));
        while (!q.isEmpty()) {
            Dot d = q.poll();
            int currentX = d.x;    //현재 x좌표
            int currentY = d.y;    //현재 y좌표
            int currentD = d.dir;    //현재 방향
            Boolean flags = false;    //4방향이 다 청소돼있거나 벽일 경우를 판단해줌.
            int nextX;
            int nextY;
            int nextD;
 
            for (int i = 0; i < 4; i++) {
                currentD = (currentD + 3) % 4;    //다음 이동할 방향
                nextX = currentX + (dx[currentD]);    //다음 이동할 X좌표
                nextY = currentY + (dy[currentD]);    //다음 이동할 Y좌표
 
                Dot nextDot = new Dot(nextX, nextY, currentD);
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                //다음 이동할 위치가  청소되지 않은 곳이라면 간다.
                if (arr[nextX][nextY] == 0) {
                    q.add(nextDot);
                    arr[nextX][nextY] = 9;
                    flags = true;
                    break;
                }
            }
            //4방향다 청소됐거나 벽일 경우에는 후진해야한다.
            if (!flags) {
                nextD = (currentD + 2) % 4;
                nextX = currentX + dx[nextD];
                nextY = currentY + dy[nextD];
 
                //만약 후진할 곳이 벽이 아니라면, 이동 그렇지 않다면 종료한다.
                if (arr[nextX][nextY] != 1) {
                    arr[nextX][nextY] = 9;
                    q.add(new Dot(nextX, nextY, currentD));
                }
            }
        }
    }
 
    //청소한 칸의 개수를 구하는 함수
    public static void Check(int[][] arr) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 9)
                    count++;
                //System.out.print(arr[i][j] + "\t");
            }
            //System.out.println();
        }
    }
}
 
class Dot {
    int x;
    int y;
    int dir;
 
    Dot(int x, int y, int dir) {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 2910 - 빈도 정렬 (자바)  (0) 2018.02.20
[BOJ] 백준 7576 - 토마토 (자바)  (0) 2018.02.20
[BOJ] 백준 5555 - 반지 (자바)  (0) 2018.02.15
[BOJ] 백준 11047 - 동전 0 (자바)  (0) 2018.02.13
[BOJ] 백준 1152 - 단어의 개수 (자바)  (1) 2018.02.13
반응형

문자열,,.


자바 중 문자열의 contains() 함수 알면 쉽게 풀 수 있다. 나는 contains 함수를 몰라서 어떻게 풀지 계속 생각했었다..

다만 링이기 때문에 끝에서 앞으로 문자열이 이어질 경우만 막으면 된다. 

방법은 바로 문자열을 복사해서 뒤에 붙여넣으면 된다.


풀이

1. 문자열 + 문자열을 해서 원형의 느낌으로 만든다. (링 이기 때문에)

2. contains() 함수를 써서 문제를 푼다.


소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String output;
        int count = 0;
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            output = br.readLine();
            output += output;
 
            if (output.contains(str)) {
                count++;
            }
        }
        System.out.println(count);
 
    }
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 7576 - 토마토 (자바)  (0) 2018.02.20
[BOJ] 백준 14503 - 로봇청소기 (자바)  (0) 2018.02.20
[BOJ] 백준 11047 - 동전 0 (자바)  (0) 2018.02.13
[BOJ] 백준 1152 - 단어의 개수 (자바)  (1) 2018.02.13
[BOJ] 백준 14502 - 연구소 (자바)  (0) 2018.02.13
반응형

Greedy..


가장 큰값부터 차근차근 계산해나가면 된다.


풀이

1. 제일 큰 값 (동전) 으로 부터 입력 받은 값과 비교하여 입력받은 값이 크면 나눈다.

나눈 값은 동전의 개수가 되며 나머지는 그 다음 다른 돈으로 바꿀 돈이 된다.

2. 돈이 0이 될때까지 반복한다.


소스

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.FileInputStream;
import java.util.*;
import java.util.stream.*;
 
class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        // Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        int M = sc.nextInt();
        int count =0;
        int[] arr=  new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }
        
            for(int i = N-1; i>=0; i--){
                if(M>=arr[i]){
                    count += M/arr[i];
                    M = M%arr[i];
                }
                
            }
            
            System.out.println(count);
        
        
    }
 
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 14503 - 로봇청소기 (자바)  (0) 2018.02.20
[BOJ] 백준 5555 - 반지 (자바)  (0) 2018.02.15
[BOJ] 백준 1152 - 단어의 개수 (자바)  (1) 2018.02.13
[BOJ] 백준 14502 - 연구소 (자바)  (0) 2018.02.13
[BOJ] 백준 2143 - 다리 만들기 (자바)  (0) 2018.02.12
반응형

문자열 처리..


단순 문자열 처리이다.

근데 정답 비율이 엄청 낮다. 왜 그럴까? 예시가 적어서..

띄어쓰기가 한칸만 있다고 생각하면 큰 오산이다.

자바에서 split(" ") 하면 끝이라 생각해서 많이 틀린것 같다.

그렇다면 어떠한 예시가 있을까?

A B C D E      F

라는 예제가 있다고 가정하자.

split()  함수를 쓰면 String 배열 중간중간 "" 값을 갖게 된다. 그래서 정답이 틀리게 나온다.

이 부분만 제거하면 성공이다.


풀이

1. 문장을 입력받는다.

2. 띄어쓰기가 연속으로 나올 수 있으니 그 경우만 조심한다. 구현은 알아서.


소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String[] str = br.readLine().split(" ");
        int count = str.length;
        for (int i = 0; i < str.length; i++) {
            if (str[i].equals("")) {
                count--;
            }
        }
        System.out.println(count);
    }
}
 
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 5555 - 반지 (자바)  (0) 2018.02.15
[BOJ] 백준 11047 - 동전 0 (자바)  (0) 2018.02.13
[BOJ] 백준 14502 - 연구소 (자바)  (0) 2018.02.13
[BOJ] 백준 2143 - 다리 만들기 (자바)  (0) 2018.02.12
[BOJ] 백준 9465 - 스티커 (자바)  (0) 2018.02.10
반응형

BFS .. DFS


문제 자체는 아주 단순한 문제이다. 바이러스가 최대한 전파되지 못하게 하는것이다. (즉 BFS나 DFS의 가지가 멀리가지 못하게 하면 된다.)

그리고 배열의 크기가 8이기 때문에 어떠한 방법을 써서 풀어도 왠만해서는 시간초과가 나지 않는다.

나는 그래서 진짜 무식하게 좌표를 일일히 계산해가며 벽을 세웠다. 진짜 못짠 코드...


풀이

1. 세개의 벽을 세운다. (벽이 설 자리는 0이 있는곳으로 세개의 벽 모두 다른 곳에 설치되어야 한다.)

   이때 벽을 설치하는 방법이 여러개가 있지만 나는 무식하게 전체 좌표를 일일히 계산했는데 인터넷에서 다른분의 코드를 보니

   0일때의 좌표를 미리 list에 저장해 논다음, list에서 빼오면 훨씬 간단히 동작한다는 것을 알게되었다.

   나는 6중 반복문을 써서 좌표를 구했지만 위의 경우 3중 반복문만 쓰면 간단히 해결 된다.

2. 세개의 벽을 모든 경우 세워보고 그때마다 BFS나 DFS로 바이러스를 퍼뜨리면 된다.

3. 나는 또 여기서 무식하게 2중 반복문으로 바이러스가 있는점을 찾았지만 이렇게 하는 것 보다 맨 처음 숫자를 입력받을 때 2의 위치를 저장해주면 2중 

   복을 계속해서 돌 필요가 없어진다. 배열이 조금만 커졋더라면 시간초과 ㅠ

4. 탐색 후 0의 갯수를 체크하여 최대 값을 저장하면 끄읏.

5. 아 그리고 벽을 세우고 바이러스를 전파했기 때문에 세개의 벽을 놓기전에 배열을 계속해서 초기화 해줘야 한다. 그래서 나는 Reset() 함수를 사용해서

   초기화시켜줌.

소스

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    static int N;
    static int M;
    static int[][] arr;
    static int[][] reset;
 
    public static void main(String args[]) throws Exception {
        //BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
 
        arr = new int[N][M];
        reset = new int[N][M];
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        Reset();
        int max = Integer.MIN_VALUE;
 
        for (int x1 = 0; x1 < N; x1++) {
            for (int y1 = 0; y1 < M; y1++) {
                //벽 세울 위치가 0이 아니면 패스
                if (reset[x1][y1] != 0)
                    continue;
                for (int x2 = 0; x2 < N; x2++) {
                    for (int y2 = 0; y2 < M; y2++) {
                        //좌표가 같으면 돌필요 없으므로 패스
                        if (x1 == x2 && y1 == y2)
                            continue;
                        //벽 세울 위치가 0이 아니면 패스
                        if (reset[x2][y2] != 0)
                            continue;
                        for (int x3 = 0; x3 < N; x3++) {
                            for (int y3 = 0; y3 < M; y3++) {
                                //좌표가 같으면 돌필요 없으므로 패스
                                if (x1 == x3 && y1 == y3)
                                    continue;
                                if (x2 == x3 && y2 == y3)
                                    continue;
                                //벽 세울 위치가 0이 아니면 패스
                                if (reset[x3][y3] != 0)
                                    continue;
 
                                //바이러스가 있는 점을 찾기 위한 반복문
                                for (int i = 0; i < N; i++) {
                                    for (int j = 0; j < M; j++) {
                                        //바이러스가 있을 때만 시뮬레이션 실행
                                        if (reset[i][j] == 2) {
                                            //세개의 벽을 세움
                                            reset[x1][y1] = 1;
                                            reset[x2][y2] = 1;
                                            reset[x3][y3] = 1;
                                            BFS(i, j);
                                        }
                                    }
                                }
                                max = Math.max(max, Check());
                                Reset();
                            }
                        }
                    }
                }
            }
        }
        System.out.println(max);
    }
 
    public static void BFS(int x, int y) {
        Queue<Dot> q = new LinkedList<Dot>();
        q.add(new Dot(x, y));
 
        while (!q.isEmpty()) {
            Dot d = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = d.x + dx[i];
                int nextY = d.y + dy[i];
 
                //배열 범위를 넘어가면 패스
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                //벽에 막혀있거나 이미 바이러스에 감염됐다면 패스
                if (reset[nextX][nextY] == 1 || reset[nextX][nextY] == 2) {
                    continue;
                }
                //바이러스 전파
                q.add(new Dot(nextX, nextY));
                reset[nextX][nextY] = 2;
            }
        }
 
    }
    //다음 시뮬레이션을 해야하므로 배열을 초기화 해줘야한다.
    public static void Reset() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                reset[i][j] = arr[i][j];
            }
        }
    }
 
    //0의 계수를 체크, 즉 안전지역 개수 체크
    public static int Check() {
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (reset[i][j] == 0)
                    count++;
            }
        }
        return count;
    }
 
}
 
class Dot {
    int x;
    int y;
 
    Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 11047 - 동전 0 (자바)  (0) 2018.02.13
[BOJ] 백준 1152 - 단어의 개수 (자바)  (1) 2018.02.13
[BOJ] 백준 2143 - 다리 만들기 (자바)  (0) 2018.02.12
[BOJ] 백준 9465 - 스티커 (자바)  (0) 2018.02.10
[BOJ] 백준 9205 - 맥주 마시면서 걸어가기 (자바)  (0) 2018.02.10
반응형

BFS + DFS


BFS 와 DFS 둘 다 사용해서 푼 문제이다.

BFS와 DFS 의 개념을 알면 힘들게 풀지는 않을 수 있다.

나는 이렇게 푸는게 맞는지 모르겠지만 풀이를 써보겠습다.


풀이

1. 나는 섬에 각각 라벨링을 하여 번호를 매겨줬다.

첫번째 섬은 2의 값으로 두번째 섬은 3의 값으로 세번째 섬은 4의 값으로 매겼다. 이때 DFS를 사용했습니다.

섬에 숫자를 다르게 매겨준 이유는 다리를 놓을때 같은 섬 사이에 다리를 놓으면 문제가 생기기 때문에 다른 값으로 설정

2. 섬의 모든 점에서 다리를 놓기 시작한다. 최단거리는 상,하,좌,우 어디에서 생길지 모르기 때문... 섬의 한 가운데라면 조건을 이용해서 다리 안놓게 해도

되는데 나는 그냥 전체 BFS 돌려버렸다. 어차피 반복문 4번만 하면 빠져 나오니깐;

3. 섬의 모든점에서 다리를 놓는데 다리는 같은섬에 놓지 못하고 바다일 때만 놓을 수 있다. 즉 다음 방문지가 0값을 가지고 있을 때 다리를 놓을 수 있다.

그리고 이미 다리를 놓은 값은 -1로 설정하여 무한루프에 빠지지 않게 설정해줘야 한다. (-1로 설정해줬기 때문에 배열을 초기화 해줘야함)

나는 배열 초기화 때문에 reset[][] , arr[][] 함수를 2개 사용 했다.

4. 다리를 놓으면서 현재 자기섬의 값이 아닌 다른 섬에 도착하였을 때 BFS를 종료시켜주면 된다.(return 함수 사용)

최단 거리를 비교하여 변수에 저장시켜주고 나중에 출력시켜주면 끄읏.


소스

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
 
import javax.rmi.ssl.SslRMIClientSocketFactory;
 
public class Main {
    static int[][] arr;
    static int[][] reset;
    static int N;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int count = 1;
    static int min = Integer.MAX_VALUE;
 
    public static void main(String args[]) throws Exception {
        //BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        reset = new int[N][N];
        arr = new int[N][N];
        
        for (int i = 0; i < N; i++) {
            String[] str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                reset[i][j] = Integer.parseInt(str[j]);
            }
        }
        //-----------------입력부------------------\\
        
        //다리를 건너기전에 해야 할 일이 하나 있다.
        //섬 마다 번호를 붙혀줘야한다. 아래 DFS는 번호를 붙혀주는 작업을 한다.
        //1번째 방문하는 섬은 2번으로 2번째는 3번으로 ...
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (reset[i][j] == 1) {
                    count++;
                    reset[i][j] = count;
                    Labeling_DFS(i, j);
                }
            }
        }
        Reset();    //arr함수를 reset 함수로 초기화 시켜줌. (복사)
        
        //가장 가까운 다리길이를 찾는 과정
        //섬에서 시작하여 다른 섬에 가장 빨리 도착할 때 값을 저장하고 돌아온다.
        //섬의 모든 지점에서 확인한다. 상하좌우에 섬이 있을 수 있고 최단거리가 될 수 있으므로
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] != 0) {
                    ShortestPath_BFS(i, j);
                    Reset();
                }
            }
        }
        System.out.println(min);
 
    }
 
    public static void Labeling_DFS(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            //좌표 넘어가면 패스
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
                continue;
            }
            //다음 갈 위치가 같은 섬이면 패스
            if (reset[nextX][nextY] == count) {
                continue;
            }
            //다음 갈 위치가 바다이면 패스
            if (reset[nextX][nextY] == 0) {
                continue;
            }
            //섬의 번호를 count로 통일한다. (count는 2,3,4 등등 순으로 증가한다)
            reset[nextX][nextY] = count;
            Labeling_DFS(nextX, nextY);
        }
 
    }
 
    public static void ShortestPath_BFS(int x, int y) {
        
        //inX, inY 는 출발 섬의 값을 저장하기위한 좌표이다.
        int inX =x;    //출발 섬의 x좌표
        int inY = y; //출발 섬의 y좌표
        Queue<Dot> q = new LinkedList<Dot>();
        q.add(new Dot(x, y,0));
 
        while (!q.isEmpty()) {
            Dot current = q.poll();
            for (int i = 0; i < 4; i++) {
                //다음 간척사업할 위치좌표와 거리 저장 변수
                int nextX = current.x + dx[i];
                int nextY = current.y + dy[i];
                int nextCount = current.count + 1;
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
                    continue;
                }
                //다음 간척할 자리가 이미 섬이라면 패스
                if (arr[nextX][nextY] == arr[inX][inY]) {
                    continue;
                }
                //다음 간척할 자리가 이미 간척한 자리라면 패스
                if(arr[nextX][nextY]==-1){
                    continue;
                }
                //다음 간척할 자리가 바다가 아니라면
                //이미 섬과 간척자리는 위에 조건에 걸렸으므로 이 조건일 때는 무조건 다른 섬이다.
                if(arr[nextX][nextY]!=0){
                    //다른 섬에 도착했을때의 최단거리를 비교하여 저장. 그리고 리턴
                    min = Math.min(min, nextCount-1);
                    return;
                }
                //간척한 자리는 -1로 놓는다. 그리고 큐에 넣는다.
                arr[nextX][nextY] = -1;
                q.add(new Dot(nextX,nextY,nextCount));
                
            }
        }
 
    }
 
    //간척사업으로 인해 -1로 변한 자리를 되돌려 놔야 다른 최단거리를 구할 수 있다.
    public static void Reset() {
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                arr[i][j] = reset[i][j];
            }
        }
    }
 
}
 
class Dot {
    int x;
    int y;
    int count;
    Dot(int x, int y,int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1152 - 단어의 개수 (자바)  (1) 2018.02.13
[BOJ] 백준 14502 - 연구소 (자바)  (0) 2018.02.13
[BOJ] 백준 9465 - 스티커 (자바)  (0) 2018.02.10
[BOJ] 백준 9205 - 맥주 마시면서 걸어가기 (자바)  (0) 2018.02.10
[BOJ] 백준 14889 - 스타트와 링크 (자바)  (2) 2018.02.09
반응형

DP...


설명하기 귀찮은데..

DP중에 쉬운문제같다. 직관적으로 보여.


풀이

배열의 위치마다 값을 저장해야하는 arr[][] 배열이 필요하고 

이전값과 함해서 최대값을 만들기 위한 dp[][] 배열이 필요하다.


이경우에 올 수 있는 경우는

1. 자신의 왼쪽 대각선 (위의 배열일 경우 왼쪽 아래, 아래 배열일 경우 왼쪽 위) 에 존재하는 값 다음에 올 수 있고

2. 자신의 왼쪽 왼쪽 에 위치한 값 다음에 올 수 있다.

이 두 값 다음에 오는거 말고는 최대값을 가질 수 없을 거같은데..?



아무튼 두 경우를 이용해 식을 만들면

dp[i][0] = Math.max(dp[i-1][1],dp[i-2][1] ) + arr[i][0];

dp[i][1] = Math.max(dp[i-1][0],dp[i-2][0] ) + arr[i][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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(new
        // InputStreamReader(System.in));
 
        int Testcase = Integer.parseInt(br.readLine());
        int[][] arr;
        int[][] dp;
        String[] str;
        for (int t = 0; t < Testcase; t++) {
            int N = Integer.parseInt(br.readLine());
            arr = new int[N+1][2];
            dp = new int[N+1][2];
            for (int i = 0; i < 2; i++) {
                str = br.readLine().split(" ");
                for (int j = 1; j <=N; j++) {
                    arr[j][i] = Integer.parseInt(str[j-1]);
                }
            }
            
            dp[1][0] = arr[1][0];
            dp[1][1] = arr[1][1];
            for(int i=2; i<=N; i++){
                dp[i][0] = Math.max(dp[i-1][1],dp[i-2][1] ) + arr[i][0];
                dp[i][1] = Math.max(dp[i-1][0],dp[i-2][0] ) + arr[i][1];
            }
            System.out.println(Math.max(dp[N][0], dp[N][1]));
        }
    }
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 14502 - 연구소 (자바)  (0) 2018.02.13
[BOJ] 백준 2143 - 다리 만들기 (자바)  (0) 2018.02.12
[BOJ] 백준 9205 - 맥주 마시면서 걸어가기 (자바)  (0) 2018.02.10
[BOJ] 백준 14889 - 스타트와 링크 (자바)  (2) 2018.02.09
[BOJ] 백준 1759 - 암호 만들기 (자바)  (0) 2018.02.09
반응형

BFS..


예제가 몇개 없어서 헤맨 문제.. 라기보단 문제 접근 자체를 완전 이상하게 접근함.

편의점의 위치가 출발점에서 가까운 순서대로 위치한 줄 알았는데그게 아님.

결국 편의점 위치를 일일히 확인해 봐야한다.


풀이

1. 시작위치(상근이네), 편의점 위치, 도착위치(페스티벌) 의 좌표 모두 하나의 클래스 배열 location[] 안에 넣어준다.

2. 시작위치로 부터 출발한다. (큐에 넣어준다.)

3. 출발하여 location[] 클래스 배열안에 있는 조건에 맞는 좌표를 방문한다.

4. 조건이란 출발위치로부터 다음 위치의 차이가 1000이하이며, 이전에 방문하지 않은 점이여야한다.

5. 페스티벌 위치와 계속 비교해주며 페스티벌 위치라면 그 즉시 성공깃발(boolean success) 만 바꾸고 종료한다.

6 성공깃발 여부에 따라 출력해주면 된다.


소스

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int Testcase = Integer.parseInt(br.readLine());
 
        for (int t = 0; t < Testcase; t++) {
            int N = Integer.parseInt(br.readLine());
            LOCATION[] location = new LOCATION[N + 2];
            int[] check = new int[N + 2];
            Queue<LOCATION> q = new LinkedList<LOCATION>();
            boolean success = false;
            String[] str;
            for (int i = 0; i < N + 2; i++) {
                str = br.readLine().split(" ");
                location[i] = new LOCATION(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
            }
            //--------------입력 끝--------------//
            
            LOCATION start = location[0];    //시작 위치
            LOCATION end = location[N + 1];    //도착 위치
            q.add(start);    //시작 위치로 부터 출발
            
            while (!q.isEmpty()) {
                LOCATION current = q.poll();
                //만약 다음에 접근할 위치가 도착 위치라면 성공깃발만 바꾸고 종료한다.
                if(current.equals(end)){
                    success = true;
                    break;
                }
                //모든 방문할 위치 중에서 거리가 1000(맥주 20병) 안에 도착 할때만 Queue에 저장한다.
                for (int i = 1; i < N + 2; i++) {
                    if (check[i] == 0 &&Math.abs(current.x - location[i].x) + Math.abs(current.y - location[i].y) <= 1000) {
                        q.add(location[i]);
                        check[i] = 1;    //왔던 위치 다시 방문 하지 않기 위해서 만들어줌
                    }
                }
            }
            if(success){
                System.out.println("happy");
            }
            else{
                System.out.println("sad");
            }
        }
    }
}
 
class LOCATION {
    int x;
    int y;
 
    LOCATION(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
cs


반응형
저작자표시 (새창열림)

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 2143 - 다리 만들기 (자바)  (0) 2018.02.12
[BOJ] 백준 9465 - 스티커 (자바)  (0) 2018.02.10
[BOJ] 백준 14889 - 스타트와 링크 (자바)  (2) 2018.02.09
[BOJ] 백준 1759 - 암호 만들기 (자바)  (0) 2018.02.09
[BOJ] 백준 1890 - 점프 (자바)  (0) 2018.02.09

+ Recent posts

티스토리툴바