티스토리 뷰

알고리즘/백준

[백준] 11403번 경로 찾기

머어하지 2018. 8. 27. 14:42

1) 생각

가중치가 없는 방향 그래프가 주어졌을 때, 해당 Vertex에서 다른 Vertex로 갈 수 있는지 여부를 파악해서 갈 수 있다면 1로 표시 없다면 0으로 표시하여 출력하라.


처음 생각

DFS를 통해 방문표시를 해가면서 탐색하면 되는 문제라고 생각하고 제출 하였지만...


시간 초과의 늪에 빠지고 말았다. 예제는 아주 잘되는데 머가 문제였을까... 정말 많이 고민했지만 계속되는 시간초과..  2가지의 문제점이 있었다.


2) 방안

1) DFS 시작의 문제점. 모든 Vertex을 탐색하기 위해서 처음에는 2중 반복문을 통해 해당 Index가 1의 값을 가지고 있으면 거기서 부터 탐색을 시작하였다. 

=> 결론은 해당 Vertex에서 다른 Vertex들을 갈 수 있냐의 문제로 일단 해당 Vertex를 집어넣고 그 점으로부터 탐색을 하면 된다. 따라서 2중 반복문을 없애고 주어진 Vertex의 개수만 큼만 반복문을 돌개하였다.


2) DFS 가지치기의 문제점. 무한 루프에 빠지지 않기위해 방문배열을 만들어 True일 경우 DFS를 진행하지 않도록 한 뒤, 재귀가 종료될 때 순차적으로 False로 만들어 다음 재귀에 대비하였다.

=> for문을 돌면서 False로 바꾼 부분 때문에 다시 들어가는 경우가 있었다. 결과로 만들고있는 배열 자체가 1일 경우 이미 이 경로는 방문했다는 증거가 되므로 결과로 만들고 있는 배열이 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int n;
    static int[][] arr,result;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        result = new int[n][n];
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }
        // 한 줄씩 갈 수 있는곳을 모두 살펴보자.
        for(int i=0;i<n;i++)
            solve(i,i);
        
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                sb.append(result[i][j]+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
    
    private static void solve(int start,int next) {
        // start(시작 점)을 따라서 갈 수 있는 곳을 다 돌아다녀본다.
        for(int i=0;i<n;i++) {
            // 원래 배열인 arr에서 1을 가르켜야 갈 수 있으며 갈 수 있다는 것은(맨 처음 next는 start)
            // start(시작 점)에서 갈 수 있으므로 1로 표시
            // result[start][i] 가 0이 아니라면 i는 이미 방문한 곳이므로 패스.
            if(arr[next][i]==1&&result[start][i]==0) {
                result[start][i] = 1;
                solve(start,i);
            }
        }
    }
}
cs


'알고리즘 > 백준' 카테고리의 다른 글

[백준] 11723번 집합  (0) 2018.08.27
[백준] 1987번 알파벳  (0) 2018.08.27
[백준] 9663번 N-Queen  (0) 2018.08.22
[백준] 14501번 퇴사  (4) 2018.08.22
[백준] 9095번 1, 2, 3 더하기  (0) 2018.08.22
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday