반응형

문제링크 : 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

티스토리툴바