99클럽 코테 스터디 17일차 TIL , 촌수계산

문제

풀이

입력으로 

첫 번째 줄에 사람 수가 주어진다.(사람은 1~n 까지로 한다.)

두 번째 줄에 촌수계산이 필요한 두 명의 번호가 주어진다.

세 번째 줄에 관계의 수가 주어진다.

네 번째 줄부터 관계의 수만큼 관계가 주어진다.

 

주어진 관계를 가지고 촌수 계산 후에 return 하면 된다.

계산이 불가할 경우 -1을 return 한다.

 

제출 1 - 오답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int answer = 0;
    static int n,b;
    static boolean[][] relation;
    static boolean flag = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        relation = new boolean[n+1][n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(br.readLine());
        for(int i=0;i<m;i++){
            StringTokenizer pc = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(pc.nextToken());
            int y = Integer.parseInt(pc.nextToken());
            relation[x][y] = true;
            relation[y][x] = true;
        }

        dfs(a);
        if(!flag) answer = -1;
        System.out.println(answer);

    }

    private static void dfs(int a) {
        if(a == b) {
            flag = true;
        }
        if(flag) return;

        for(int i=1;i<=n;i++){
            if(!relation[a][i]) continue;
            if(flag) break;
            relation[a][i] = false;
            relation[i][a] = false;
            answer ++;
            dfs(i);
            relation[a][i] = true;
            relation[i][a] = true;
        }
    }
}

 

flag를 사용하여 찾았을 경우 나간다.

answer를 늘리기만 하고 줄어드는 것을 고려하지 않았다.

제출 2 - 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int answer = 0, cnt = 0;
    static int n,b;
    static boolean[][] relation;
    static boolean flag = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        relation = new boolean[n+1][n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(br.readLine());
        for(int i=0;i<m;i++){
            StringTokenizer pc = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(pc.nextToken());
            int y = Integer.parseInt(pc.nextToken());
            relation[x][y] = true;
            relation[y][x] = true;
        }

        dfs(a);
        if(!flag) answer = -1;
        System.out.println(answer);

    }

    private static void dfs(int a) {
        if(a == b) {		//찾던 값과 같으면 촌수 answer에 넣어주고 flag 변환
            answer = cnt;
            flag = true;
        }
        if(flag) return;	//flag return

        for(int i=1;i<=n;i++){
            if(flag) break;		//flag break
            if(!relation[a][i]) continue;	//이어져있지 않으면 패스
            relation[i][a] = false;	//연결 끊기
            cnt++;
            dfs(i);
            cnt--;
            relation[i][a] = true;
        }
    }
}

 

cnt를 사용하여 목표값과 값이 같아지면 answer에 촌수를 넣어준다.

제출 3 - 리팩토링

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    private static int n, target;
    private static boolean[][] relation;
    private static boolean[] visited;
    private static int result = -1;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        relation = new boolean[n + 1][n + 1];
        visited = new boolean[n + 1];

        StringTokenizer startAndTarget = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(startAndTarget.nextToken());
        target = Integer.parseInt(startAndTarget.nextToken());

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            StringTokenizer xy = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(xy.nextToken());
            int y = Integer.parseInt(xy.nextToken());
            relation[x][y] = true;
            relation[y][x] = true;
        }

        dfs(start,0);
        System.out.println(result);
    }

    private static void dfs(int current, int count){
        if(current == target){
            result = count;
            return;
        }
        visited[current] = true;

        for(int i=1;i<=n;i++){
            if(relation[current][i] && !visited[i]){
                dfs(i, count+1);
            }
        }

        visited[current] = false;
    }
}

 

visited 배열을 만들어서 방문여부를 확인하게 했다.

이를 통해 flag도 없애고 불필요한 코드들을 없앴다.

TIL

• DFS문제 해결