[알고리즘풀이]백준 11403 : 경로 찾기 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 11043번 경로 찾기를 풀었습니다. 이를 정리해보고자 합니다.

11403번: 경로 찾기

 

본문

1) 문제

2) 과정

이번 문제를 푸는데는 30분 정도 걸렸어요. 에러도 한번없이 빠르게 성공한 문제였답니다. 그 정도로 입력부분만 처리할줄알면 기본 탐색 알고리즘(좀 더 나아가면 다익스트라알고리즘)과 별반 다를게 없던 간단한 문제였습니다.  그리고 개선하는데 좀 오랜 시간을 투자하여 속도를 2배감축시켰답니다! 그 과정은 깃헙에서 확인해주세요 :)

맛보기 개선과정 초반

맛보기 개선과정 최종

0) i->j에 맞춰 값을 orgArr 배열에 넣어준다.
1) 각 줄마다의 dp를 계산하여 출력하는 문제이기 때문에 탐색을 시작하곤 for문으로 각 줄마다 큐에 줄번호(i)를 넣고 visited를 new해준다.
2) 큐가 빌때까지 그 줄의 시작 인덱스의 노드부터 갈수있는 노드들을  dp와 visited로 체크하며 탐색한다.
3) 모든 탐색이 끝나면 dp의 값을 순서대로 모두 출력한다.

 

그럼 빠르게 Input,Logic,Output으로 문제 풀이를 나눠 보여드릴게요 :)

*** 설명은 주석으로 충분한 것 같아서 따로 설명은 달지 않았습니다. ***

 

2-1) Input

   // Variable
    private static BufferedReader br;
    private static StringTokenizer st;
    public static void main(String[] args) throws IOException{
        // Input
        br = new BufferedReader(new InputStreamReader(System.in));
        readLine();
        int n = nextInt(); // 노드의 수 & 행/열의 개수

        ArrayList<Integer>[] orgArr = new ArrayList[n+1]; // 연결정보를 담아낼 배열
        for(int i=0;i<n;i++){
            readLine();
            orgArr[i] = new ArrayList<>();
            for(int j=0;j<n;j++) if(nextInt()==1) orgArr[i].add(j);
        }
    }
    // Method - for read input values
    public static void readLine() throws IOException { st = new StringTokenizer(br.readLine());}
    public static int nextInt(){ return Integer.parseInt(st.nextToken());}

 

2-2) Logic & Output

        // Logic
        // initialize settings
        Queue<Integer> q= new PriorityQueue<>(); // 탐색을 윈한 큐
        boolean[] visited; // 각 줄에서의 방문여부를 체크하고자 사용하는 배열
        StringBuilder sb = new StringBuilder(); // 출력할 내용을 담고자 사용하는 StringBuilder
        // start all line searching 
        for(int i=0;i<n;i++) {
            // reinitialize 
            visited = new boolean[n+1]; // 각 줄(i)마다 new해준다.
            q.add(i);
            // start one line searching
            while(!q.isEmpty()){
                // get a number
                int cur = q.poll();
                for(int next : orgArr[cur]){
                    // check visited condition and add the next into q
                    if(visited[next]) continue;
                    visited[next] = true;
                    q.add(next);
                }
            }
            // 출력부분을 미리 계산하여 시간과 불필요한 메모리 사용을 줄임
            for(int j=0;j<n;j++) {
                // i란 노드가(해당 i줄이) j에 방문한적 있다면 1을 추가하고 아니면 0을 추가
                if(visited[j]) sb.append("1 ");
                else sb.append("0 ");
            } sb.replace(2*n*(i+1)-1, 2*n*(i+1), "\n"); // 마지막 인덱스값만 변경해줌.
        }

        // Output
        System.out.println(sb.toString());

 

3) 전체코드

그렇게 완성된 코드는 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!

소요시간, 아이디어, 에러로그 등 더 자세히 보실 수 있습니다.

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/shortest_path/BOJ11403.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비