문제링크 : https://www.acmicpc.net/problem/2225

 

2225번: 합분해

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

높은 정답률(현재 42%)에 비해 개인적으로 푸는데 고생을 좀 했던 문제이다. 총 2가지 풀이법을 소개할 것인데, 1. 내가 이 문제를 처음 푼 방법, 2. 인터넷에서 검색할 수 있는 일반적인(?) 방법이다.

 

N = 5, K = 3일 때를 직접 일일히 세어가면서 구한다고 생각해보자. 일단 2개로 먼저 쪼개보면, (5, 0), (4, 1), (3, 2), (2, 3), (1, 4), (0, 5)가 될 것이다. 여기서 한 번 더 나눠야 하는데, 이 때는 마지막 수를 다시 2개로 쪼갠다고 생각하면 된다. 그러면 (5, 0, 0), (4, 1, 0), (4, 0, 1), (3, 2, 0), (3, 1, 1), (3, 0, 2)... 이 식으로 될텐데 아래 그림을 보면 이해가 될 것이다.

여기서 내가 고려한 점은

1. K를 위와 같은 방식으로 계속 증가시키면서, 마지막 수의 개수를 카운트한다. (마지막 수만 경우의 수에 영향을 미치므로)

2. 마지막 수는 0 ~ N까지의 수인데, K가 증가할 때 임의의 i의 개수는 바로 직전 마지막 수들 중 i보다 큰 수들의 개수를 모두 더한 값이 된다. (위의 그림을 예로 들면, 3의 개수는 바로 직전의 3 ~ 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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[] cnt = new int[n + 1];
        cnt[n] = 1;
        
        for(int i = 2; i <= k; i++) {
            int[] tmp = new int[n + 1];
            tmp[n] = 1;
            
            for(int j = n - 1; j >= 0; j--) {
                tmp[j] = tmp[j + 1] + cnt[j];
                tmp[j] %= 1_000_000_000;
            }
            
            cnt = tmp;
        }
        
        long sum = 0;
        
        for(int i = 0; i <= n; i++) {
            sum += cnt[i];
            sum %= 1_000_000_000;
        }
        
        System.out.println(sum);
    }
}
 
  

 

이번에는 인터넷에서 흔히 볼 수 있는 일반적인(?) 풀이법에 대한 설명이다.

 

N = 5, K = 3일 때를 구한다고 가정해보면, 

0 ~ 5의 수 중 3개를 선택하여 5를 만드는 경우의 수 = 첫번째 수를 0으로 선택하고, 0 ~ 5의 수 중 2개를 선택하여 5를 만드는 경우의 수 + 첫번째 수를 1으로 선택하고, 0 ~ 4의 수 중 2개를 선택하여 4를 만드는 경우의 수 .....

이런 식으로 될텐데, 수식화 해보면 아래와 같다.

 

(N=5, K=3) = (N=5, K=2) + (N=4, K=2) + (N=3, K=2) + (N=2, K=2) + (N=1, K=2) + (N=0, K=2)

 

여기서 우리는 규칙성을 확인할 수 있는데, 이를 다시 수식화 해보면 아래와 같다.

 

(N=i, K=j) = (N=i, K=j-1) + (N=i-1, K=j-1) + (N=i-2, K=j-1) + ..... + (N=0, K=j-1)

<-> (N=i, K=j) = (N=i, K=j-1) + (N=i-1, K=j)

 

위에서 얻어낸 점화식과 함께 아래사항을 초기값으로 이용하면 답을 도출해낼 수 있다.

1. K = 1 일 때 경우의 수는 1이다.

2. N = 1 일 때 경우의 수는 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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[][] dp = new int[n + 1][k + 1];
        
        for(int i = 1; i <= k; i++) {
            dp[1][i] = i;
        }
        
        for(int i = 1; i <= n; i++) {
            dp[i][1] = 1;
        }
        
        for(int i = 2; i <= n; i++) {
            for(int j = 2; j <= k; j++) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1_000_000_000;
            }
        }
        
        System.out.println(dp[n][k]);
    }
}
  

 

두 코드 모두 동일한 시간복잡도를 가지고 있지만, 개인적으로 두 번째 풀이방법이 더 기억하기도, 이해하기도 쉬운 것 같다. 

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준(BOJ) 2004 : 조합 0의 개수 (JAVA)  (0) 2020.02.04
백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30
백준(BOJ) 1261 : 알고스팟 (JAVA)  (0) 2020.01.29

문제링크 : https://www.acmicpc.net/problem/1654

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

www.acmicpc.net

 

결론부터 말하자면, 이 문제는 이분탐색 문제이다. 이분탐색으로 풀면된다는 사실을 알고 이 문제를 보면, 사실 그다지 어려운 문제는 아니다. 근데 이분탐색으로 풀면 되겠다고 생각해내는 것, 그게 어렵다. 어쩌면 그게 알고리즘의 전부일지도 모르겠다...ㅠㅠ

 

그리고 이 문제의 정답비율이 유독 낮은(현재 19%) 이유를 필자가 예상하건데, 함정이 있다. 문제에서는 랜선의 길이가 2^31 -1(int의 최댓값)보다 작거나 같은 자연수라고 나오는데, 이는 랜선의 길이를 int로 해도 되겠다라고 생각하게 만들지만 그렇지 않다. 이분 탐색을 위해 두 길이를 더하는 순간 넘어가버리게 된다... 코드는 아래와 같다.

 

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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] wires = new int[k];
        long sum = 0;
        
        for(int i = 0; i < k; i++) {
            wires[i] = Integer.parseInt(br.readLine());
            sum += wires[i];
        }
        
        long answer = 1;
        long left = 1;
        long right = sum / n;
        
        while(left <= right) {
            long mid = (left + right) / 2;
            
            int cnt = checkPossibleLineNo(wires, mid, k);
            
            if(cnt >= n) {
                left = mid + 1;
                
                if(mid > answer) {
                    answer = mid;
                }
            } else {
                right = mid - 1;
            }
        }
        
        System.out.println(answer);
    }
 
    private static int checkPossibleLineNo(int[] wires, long mid, int k) {
        int cnt = 0;
        
        for(int i = 0; i < k; i++) {
            cnt += wires[i] / mid;
        }
        
        return cnt;
    }
}
 
  

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30
백준(BOJ) 1261 : 알고스팟 (JAVA)  (0) 2020.01.29
백준(BOJ) 9466 : 텀 프로젝트 (JAVA)  (0) 2020.01.29

문제링크 : https://www.acmicpc.net/problem/1931

 

1931번: 회의실배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

 

어떻게 하면 가장 적은 횟수의 비교를 통해 최댓값을 얻어낼 수 있을지를 생각해내는 게 중요한 문제이다. 필자는 처음에 정말 단순하게 '길이(Duration)가 짧은 회의부터 우선적으로 넣으면 되지 않을까?'라고 생각을 했으나, 이 경우에는 회의를 넣어도 되는지 판단하는 시점에서 이미 추가된 "모든" 회의들과 겹치는 부분이 없는지를 비교해야했다. 이 경우의 시간복잡도는 O(N^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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[n];
        
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end);
        }
        
        Arrays.sort(meetings);
        
        int cnt = 1;
        Meeting pastMeeting = meetings[0];
        
        for(int i = 1; i < n; i++) {
            Meeting meeting = meetings[i];
            
            if(!meeting.intersect(pastMeeting)) {
                cnt++;
                pastMeeting = meetings[i];
            }
        }
        
        System.out.println(cnt);
    }
    
    private static class Meeting implements Comparable<Meeting> {
        private int start;
        private int end;
        
        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        public int getStart() {
            return start;
        }
 
        public int getEnd() {
            return end;
        }
 
        @Override
        public int compareTo(Meeting obj) {
            return this.end - obj.getEnd();
        }
        
        public boolean intersect(Meeting obj) {
            return obj.getStart() < this.end && obj.getEnd() > this.start;
        }
    }
}
 
  

 

상위권 풀이들과 비교해보니, 어째 시간이 좀 더 길게 나왔다. 차이를 분석해보니, 굳이 겹치는(intersect) 여부를 보지 않고, 바로 이전의 end값과 비교시점의 start만 비교하면 되더라. 이 경우에는 오버라이드하는 함수 "compareTo" 에 조건이 일부 추가된다. 그 이유는 길이가 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
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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[n];
        
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end);
        }
        
        Arrays.sort(meetings);
        
        int cnt = 1;
        int cursor = meetings[0].getEnd();
        
        for(int i = 1; i < n; i++) {
            Meeting meeting = meetings[i];
            
            if(meeting.getStart() >= cursor) {
                cnt++;
                cursor = meeting.getEnd();
            }
        }
        
        System.out.println(cnt);
    }
    
    private static class Meeting implements Comparable<Meeting> {
        private int start;
        private int end;
        
        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        public int getStart() {
            return start;
        }
 
        public int getEnd() {
            return end;
        }
 
        @Override
        public int compareTo(Meeting obj) {
            int ret = this.end - obj.getEnd();
            
            if(ret == 0) {
                ret = this.start - obj.getStart();
            }
            
            return ret;
        }
    }
}
 
 s

 

저작자표시

'알고리즘' 카테고리의 다른 글

백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1261 : 알고스팟 (JAVA)  (0) 2020.01.29
백준(BOJ) 9466 : 텀 프로젝트 (JAVA)  (0) 2020.01.29

문제링크 : https://www.acmicpc.net/problem/1261

 

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다.

www.acmicpc.net

 

높은 정답률(현재 38%)에 비해 나에게는 정말 어려운 문제였다. 처음에는 DFS와 백트래킹을 이용해 풀어보려고 했으나 시간초과가 나왔다. 그도 그럴 것이 백트래킹의 시간복잡도는 O(2^N)인데, 여기서 주어진 N과 M의 범위를 생각했을 때 최악의 경우 2^10000번의 연산이 필요하다...;;;; 백트래킹을 사용해 아깝게(?) 통과하지 못한 코드는 아래와 같다.

 

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
 
public class Main {
    private static int[] di = {-1, 1, 0, 0};
    private static int[] dj = {0, 0, -1, 1};
    private static int min = Integer.MAX_VALUE;
    private static int m;
    private static int n;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        
        boolean[][] maze = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] temp = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                maze[i][j] = temp[j] == '0' ? true : false;
            }
        }
        
        boolean[][] visited = new boolean[n][m];
        
        dfs(maze, visited, 0, 0, 0);
        
        System.out.println(min);
    }
 
    private static void dfs(boolean[][] maze, boolean[][] visited, int i, int j, int cnt) {
        visited[i][j] = true;
        
        if(cnt >= min) {
            return;
        }
        
        if(i == n - 1 && j == m - 1) {
            if(cnt < min) {
                min = cnt;
            }
            
            return;
        }
        
        for(int k = 0; k < 4; k++) {
            int nextI = i + di[k];
            int nextJ = j + dj[k];
            
            if(nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < m && !visited[nextI][nextJ]) {
                if(maze[nextI][nextJ]) {
                    dfs(maze, visited, nextI, nextJ, cnt);
                } else {
                    dfs(maze, visited, nextI, nextJ, cnt + 1);
                }
                
                visited[nextI][nextJ] = false;
            }
        }
    }
}
 
  

 

백트래킹으로는 풀이가 불가능하다는 것을 깨닫고 BFS도 생각해보았으나, 한 번 방문된 곳이 다른 경우의 수에서 또 방문이 가능해야한다는 점을 해결하기 힘들었다. 사실 이 점 때문에 DFS 백트래킹을 처음 생각했던 것이었다. 모든 시점마다 boolean 배열을 추가해서 풀어볼까라는 생각도 해보았으나, 그 경우에는 메모리가 터질 것이었다. 나는 고뇌에 빠졌고, 결국 구글링을 통해 Deque를 이용하면 된다는 사실을 알아냈다. (우오오오오오오!!!)

특정 방에서 다음 방으로 넘어가는 단계에서, 4개의 후보 중 빈방으로 이동하는 것이 그 시점을 기준으로 가장 벽을 최소로 꺨 수 있는 방법일 것이다. 따라서 빈방으로 이동한 시점을 Deque의 앞쪽에 위치시키고(addFirst), 벽을 부순 시점을 Deque의 뒷쪽에 위치시킴으로써(addLast) 빈방으로 이동한 시점에 무조건 우선순위를 주게되면 굳이 visited에 대해 고민할 필요가 없어진다. 한 번 방문했을 때의 벽을 부순 횟수가 무조건 최소값이 되기 때문이다. 코드는 아래와 같다.

 

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
 
public class Main {
    private static int[] di = {1, -1, 0, 0};
    private static int[] dj = {0, 0, 1, -1};
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        boolean[][] isEmpty = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] temp = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                if(temp[j] == '0') {
                    isEmpty[i][j] = true;
                }
            }
        }
        
        int min = bfs(isEmpty, n, m);
        
        System.out.println(min);
    }
    
    private static int bfs(boolean[][] isEmpty, int n, int m) {
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        Deque<Point> deque = new ArrayDeque<Point>();
        deque.offer(new Point(0, 0, 0));
        
        while(!deque.isEmpty()) {
            Point poll = deque.poll();
            int i = poll.getI();
            int j = poll.getJ();
            int cnt = poll.getCnt();
            
            if(i == n - 1 && j == m - 1) {
                return cnt;
            }
            
            for(int k = 0; k < 4; k++) {
                int nextI = i + di[k];
                int nextJ = j + dj[k];
                
                if(nextI >= 0 && nextJ >= 0 && nextI < n && nextJ < m && !visited[nextI][nextJ]) {
                    visited[nextI][nextJ] = true;
                    
                    if(isEmpty[nextI][nextJ]) {
                        deque.addFirst(new Point(nextI, nextJ, cnt));
                    } else {
                        deque.addLast(new Point(nextI, nextJ, cnt + 1));
                    }
                }
            }
        }
        
        return -1;
    }
 
    private static class Point {
        private int i;
        private int j;
        private int cnt;
        
        public Point(int i, int j, int cnt) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
 
        public int getI() {
            return i;
        }
 
        public int getJ() {
            return j;
        }
 
        public int getCnt() {
            return cnt;
        }
    }
}
  

 

끝으로, 이 문제를 다 풀고 나니 알고리즘 분류가 '다익스트라 알고리즘'으로 되어있는 것을 알 수 있었다. 올바른 방법으로 풀었는지는 알 수 없으나;; 참고 삼아 공유해본다. 코드는 아래와 같으며, 다익스트라 알고리즘에 대해 참고했던 사이트 링크를 남긴다.  https://mattlee.tistory.com/50

 

<dijkstra의 최단="" 경로="" 알고리즘=""> 기본개념과 알고리즘</dijkstra의>

# 최단 경로 최단 경로(shortest path)문제는 정점 u와 정점 v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제다. 간선의 가중치는 경우에 따라 비용, 거리, 시간 등으로 해석될 수 있다...

mattlee.tistory.com

 

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
 
public class Main {    
    private static int[] di = {1, 0, -1, 0};
    private static int[] dj = {0, 1, 0, -1};
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        if(m == 1 && n == 1) {
            br.readLine();
            System.out.println(0);
            return;
        }
        
        boolean[][] visited = new boolean[n][m];
        short[][][][] wallInfo = new short[n][m][n][m];
        
        short[][] map = new short[n][m];
        
        for(int i = 0; i < n; i++) {
            char[] row = br.readLine().toCharArray();
            
            for(int j = 0; j < m; j++) {
                map[i][j] = (short) (row[j] - 48);
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < n; k++) {
                    for(int h = 0; h < m; h++) {
                        wallInfo[i][j][k][h] = 10000;
                    }
                }
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < 4; k++) {
                    int newI = i + di[k];
                    int newJ = j + dj[k];
                    
                    if(newI >= 0 && newI < n && newJ >= 0 && newJ < m) {
                        wallInfo[i][j][newI][newJ] = map[newI][newJ];
                    }
                }
            }
        }
        
        visited[0][0] = true;
        short[][] distance = wallInfo[0][0];
        
        while(true) {
            int minI = Integer.MAX_VALUE;
            int minJ = Integer.MAX_VALUE;
            int min = Integer.MAX_VALUE;
            
            for(int a = 0; a < n; a++) {
                for(int b = 0; b < m; b++) {    
                    if(!visited[a][b] && distance[a][b] < min) {
                        min = distance[a][b];
                        minI = a;
                        minJ = b;
                    }
                }
            }
            
            if(minI == n - 1 && minJ == m - 1) {
                break;
            }
            
            visited[minI][minJ] = true;
            
            for(int a = 0; a < n; a++) {
                for(int b = 0; b < m; b++) {
                    if(!visited[a][b]) {
                        if(distance[a][b] > distance[minI][minJ] + wallInfo[minI][minJ][a][b]) {
                            distance[a][b] = (short) (distance[minI][minJ] + wallInfo[minI][minJ][a][b]);
                        }
                    }                
                }
            }
        }
        
        System.out.println(distance[n - 1][m - 1]);
    }
}
 
 
  

 

 

'알고리즘' 카테고리의 다른 글

백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30
백준(BOJ) 9466 : 텀 프로젝트 (JAVA)  (0) 2020.01.29

문제링크 : https://www.acmicpc.net/problem/9466

 

9466번: 텀 프로젝트

문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=

www.acmicpc.net

각 노드를 연결했을 때, 순환사이클에 속하지 못하는 노드의 갯수를 구하는 문제이다.

첫번째 풀이를 할 때 고려한 점은 다음과 같다.

1. 누구의 선택도 받지 못한 학생부터 탐색(dfs)을 시작해서 중복 탐색을 제거한다.
2. 순환사이클안에 포함된 노드만 두 번 이상 탐색이 될 것이다.
3. 누구의 선택도 받지 못한 학생에서만 탐색을 시작하기 때문에, 폐쇄된(곁가지가 없는) 순환사이클을 이루는 노드들의 경우(예: 1-> 2-> 3 -> 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
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] selectedIdx = new int[n + 1];
            boolean[] chosen = new boolean[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 1; j <= n; j++) {
                selectedIdx[j] = Integer.parseInt(st.nextToken());
                chosen[selectedIdx[j]] = true;
            }
            
            boolean[] visited = new boolean[n + 1];
            boolean[] revisited = new boolean[n + 1];
            
            for(int j = 1; j <= n; j++) {
                if(!chosen[j]) {
                    boolean[] localVisited = new boolean[n + 1];
                    dfs(selectedIdx, j, localVisited, visited, revisited);
                }
            }
            
            int cnt = 0;
            
            for(int j = 1; j <= n; j++) {
                if(visited[j] && !revisited[j]) {
                    cnt++;
                }
            }
            
            sb.append(cnt + "\n");
        }
        
        System.out.println(sb);
    }
 
    private static void dfs(int[] selectedIdx, int j, boolean[] localVisited, boolean[] visited, boolean[] revisited) {
        if(localVisited[j]) {
            revisited[j] = true;
        } else {
            visited[j] = true;
            localVisited[j] = true;
        }
        
        if(!revisited[selectedIdx[j]]) {
            dfs(selectedIdx, selectedIdx[j], localVisited, visited, revisited);
        }
    }
}
  

하지만 이 경우, 이미 순환임이 체크된 사이클에 대해 중복된 탐색이 이루어질 수 있는 여지가 있다.

 

필자의 그림 실력을 이해바라며...;; 1번으로 탐색 후에 2번으로 탐색할 경우, 위의 코드로는 또 한번 순환사이클을 체크해야한다.

 

따라서 두 번째로 문제를 풀 때는 다음과 같은 점을 고려했다.

 

1. 순환사이클에 포함되지 않는 노드를 세는 것이 아니라, 순환사이클에 속하는 노드의 갯수를 센 다음 전체에서 빼면 된다.

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
 
public class Main {    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] selectedIdx = new int[n + 1];
            boolean[] chosen = new boolean[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 1; j <= n; j++) {
                selectedIdx[j] = Integer.parseInt(st.nextToken());
                chosen[selectedIdx[j]] = true;
            }
            
            Test test = new Test(selectedIdx, chosen, n);
            
            
            sb.append(test.solve() + "\n");
        }
        
        System.out.println(sb);
    }
    private static class Test {
        private int[] selectedIdx;
        private boolean[] chosen;
        private int n;
        private int teamCnt = 0;
        
        public Test(int[] selectedIdx, boolean[] chosen, int n) {
            this.selectedIdx = selectedIdx;
            this.chosen = chosen;
            this.n = n;
        }
 
        public int solve() {
            boolean[] visited = new boolean[n + 1];
            boolean[] resolved = new boolean[n + 1];
            
            for(int j = 1; j <= n; j++) {
                if(!chosen[j] && !resolved[j]) {
                    dfs(selectedIdx, j, visited, resolved);
                }
            }
                        
            for(int j = 1; j <= n; j++) {
                if(!visited[j]) {
                    teamCnt++;
                }
            }
            
            return n - teamCnt;
        }
        
        private void dfs(int[] selectedIdx, int j, boolean[] visited, boolean[] resolved) {
            visited[j] = true;        
            int next = selectedIdx[j];
            
            if(!visited[next]) {
                dfs(selectedIdx, next, visited, resolved);
            } else {
                
                if(!resolved[next]) {
                    
                    for(int i = next; i != j; i = selectedIdx[i]) {
                        teamCnt++;
                    }
                    
                    teamCnt++;
                }            
            }
            
            resolved[j] = true;
        }
    }    
}
 
  

필자는 항상 알고리즘 문제를 풀고나면, 내 소스의 걸린 시간 및 메모리를 상위권 사람들과 비교하면서 내가 올바르게 풀었는지의 여부를 판단하는데, 상위권 소스와 같은 로직을 썼음에도 불구하고 시간이 그 사람들처럼 줄어들지 않아서 차이점을 살펴보니, static class를 선언한 후 인스턴스 메서드를 사용하는 것이었다. 구글링을 통해 이유를 검색해보았으나 아직 찾질 못하였으니 혹시 아는 분은 댓글 남겨주시길 간절히 바라옵니다...^^;

 

 

'알고리즘' 카테고리의 다른 글

백준(BOJ) 1697 : 숨바꼭질 (JAVA)  (0) 2020.02.03
백준(BOJ) 2225 : 합분해 (JAVA)  (0) 2020.02.02
백준(BOJ) 1654 : 랜선 자르기 (JAVA)  (0) 2020.01.31
백준(BOJ) 1931 : 회의실배정 (JAVA)  (0) 2020.01.30
백준(BOJ) 1261 : 알고스팟 (JAVA)  (0) 2020.01.29

+ Recent posts

티스토리툴바