보석 쇼핑(2020 Kakao Internship)

문제풀이

"진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매"

효율성 테스트도 있는 걸로 보아 이중 for문으로 접근하면 안되겠다 싶었다. 그래서 모든 종류의 보석을 포함하는 가장 짧은 구간을 탐색하기 위해 투포인터즈 알고리즘으로 접근하였다.

Two Pointers Algorithm : 일차원 배열에서 두 개의 포인터를 이용해 원하는 값을 찾는 알고리즘

🤔 포함해야 할 보석의 종류?

우선은 모두 담아야 하는 보석의 종류가 무엇이 있는지 알아야 한다. 따라서 HashSet에 진열된 보석들(gems)을 set에 추가해주었다.

🤔 포인터 증감 조건

이제 gems를 탐색할 구간의 시작(left)과 끝(right)을 초기화한 뒤, 구간 증감 조건을 설정해보자.

일단은 보석을 담을 HashMap을 만들었다. 장바구니 역할로서, 보석의 종류를 key, 담긴 보석의 갯수를 value로 갖는다.

1. map에 보석을 담고 right를 늘려가면서 탐색구간을 넓힌다.

2. map의 key의 갯수와 set의 사이즈가 같아지면 모든 보석이 담겼다는 뜻이다! 이제 우리가 탐색할 수 있는 최대 범위가 정해졌다. 다시 포인터를 좁혀가면서 최소 간격을 추출해보자.

3. 시작이 끝을 넘어가지 않는 선에서, 만약 현재 시작 포인트(left)가 가리키는 인덱스의 보석의 value가 1 이상이라면 그 보석은 제외해도 좋다. map의 value를 1 줄이고 left 한 칸 이동해 간격을 좁혀준다.

3-1. 만약 보석이 1 이하라면 간격이 길이가 최소인지 확인해야 한다. 현재 탐색 길이(right - left)보다 이전 탐색 구간(distance)를 비교해서 현재 탐색 길이가 더 짧다면 distance를 재설정해주고, answer의 간격을 나타내는 값도 재설정해준다.

소스코드

import java.util.HashMap;
import java.util.HashSet;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        // 보석 종류 탐색
        HashSet<String> set = new HashSet<>();
        for(String gem : gems) set.add(gem);
        // 담은 보석의 종류와 개수 세기
        HashMap<String, Integer> cart = new HashMap<>();

        int left = 0;
        int right = 0;
        int distance = gems.length + 1;

        while (right < gems.length) {
            cart.put(gems[right], cart.getOrDefault(gems[right], 0) + 1);
            right++;

            if (cart.size() == set.size()) {
                while (left < right) {
                    if (cart.get(gems[left]) > 1) {
                        cart.replace(gems[left], cart.get(gems[left]) - 1);
                        left += 1;
                    } else if (distance > (right - left)) {
                        distance = right - left;
                        answer[0] = left + 1;
                        answer[1] = right;
                        break;
                    } else break;
                }
            }
        }
        return answer;
    }
}

불량 사용자 (2019 Kakao Winter Internship)

문제풀이

제재 아이디 목록(banned_id)의 각 아이디에 해당하는 모든 조합의 경우의 수를 구해야 하기 때문에 DFS를 활용해 가능한 모든 조합 구해보기로 했다. 그리고 구한 조합을 HashSet에 저장하여 중복값을 제거하고, HashSet의 사이즈를 반환하면 경우의 수를 구할 수 있다.

🤔 제재 아이디와 유저 아이디 비교 방법?

유저 아이디 문자열과 제재 아이디 문자열을 비교해서 동일한 패턴을 가지고 있는지 비교해야 하기 때문에 String.matches() 메서드를 이용했다.

contains() VS matches()

• contains() : 인자로 전달된 문자열의 존재 여부에 관한 결괏값 반환
• matches() : 정규표현식을 인자로 받고 동일한 패턴의 문자열인지에 관한 결괏값 반환

정규식에서는 '.' 이 어떤 문자 1개를 의미하기 때문에 제제 아이디에서 '***'로 표시된 부분을 '.**'으로 replace 해주었다.

🤔 DFS 활용한 조합 구하기

이제 깊이우선탐색을 활용해 유저 ID에서 제재 ID에 해당하는 아이디를 탐색하고 제재 ID의 모든 조합을 구해보자.

유저 ID 목록을 탐색하면서 아직 탐색하지 않았고, 제재 ID와 패턴이 동일한 문자열을 조합이 될 result 문자열에 추가해준다. 이때 다른 제재 아이디와의 구분을 위해 공백을 두어 넣어주었다.

그리고 제재 ID에 해당하는 ID를 모두 찾았다면(index == banned_id.length) 조합을 HashSet에 넣어주었다. 이때 주의할 점이 있다. 문제의 제한사항을 보면

"제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다."

라는 항목이 있다. 즉 "A B" 나 "B A" 나 같다는 말이다. 따라서 공백으로 나눈 조합 문자열(result)을 공백을 기준으로 String[] 배열로 변환하여 Arrays.sort() 메서드를 이용해 사전순으로 한 번 정렬해준 뒤 , 다시 새 문자열에 추가하여 조합 값을 한 번 가공해주었다. 가공한 조합은 이제 HashSet에 들어갈 수 있다!

깊이우선탐색이 끝나면 제재 ID 패턴에 해당하는 아이디 조합의 모든 경우의 수가 HashSet 안에 들어가 있을 것이다. 그럼 HashSet의 size()만 반환해주면 된다.

소스코드

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    HashSet<String> banned_id_list;
    boolean[] visited;
    private void getBannedId_dfs(int index, String result, String[] user_id, String[] banned_id) {
        if (index == banned_id.length) {
            String[] arr = result.split(" ");
            Arrays.sort(arr);
            String res = "";
            for(String id : arr) {
                res += id;
            }
            banned_id_list.add(res);
            return;
        }
        for(int i = 0; i < user_id.length; i++) {
            if (!visited[i] && user_id[i].matches(banned_id[index])) {
                visited[i] = true;
                getBannedId_dfs(index + 1, result + " " + user_id[i], user_id, banned_id);
                visited[i] = false;
            }
        }
    }
    public int solution(String[] user_id, String[] banned_id) {
        banned_id_list = new HashSet<>();
        // 정규식 활용 위한 제재 아이디 형식 변환
        for(int i = 0; i < banned_id.length; i++) {
            banned_id[i] = banned_id[i].replace('*', '.');
        }
        visited = new boolean[user_id.length];
        getBannedId_dfs(0, "", user_id, banned_id);

        return banned_id_list.size();
    }
}

후기

Level3 문제답게, 그리고 카카오 문제답게 DFS도 조건에 고려해야 할 사항들이 많이 있더라.. 그리고 정규식을 이용해서 문자열 패턴 비교를 간단히 한다든가, HashSet을 이용해 경우의 수의 중복을 제거한다든가 문제 푸는 센스가 필요한 듯 하다. Level 3 문제는 역시 쉽지 않다..!

https://www.acmicpc.net/problem/1699

문제풀이

Bottom-Up 방식을 이용한 DP를 활용하여 배열을 구성하였다. 일단 최대값은 1의 제곱으로만 구성된 경우이다. 따라서 자기 자신의 값인, dp[i] = i 로 초기화한다. 그리고 가장 작은 제곱수부터 가장 가까운 제곱수까지 루프를 돌면서 최소 개수를 찾는다.

예를 들어서 8을 제곱수의 합으로 나타낼 때, 그 항의 최소 개수를 구해보자.

1 = 1^2 2 = 1^2 + 1^2 3 = 1^2 + 1^2 + 1^2 4 = 1^2 + 1^2 + 1^2 + 1^2 , 2^2 5 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 , 2^2 + 1^2 6 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 , 2^2 + 1^2 + 1^2 7 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 , 2^2 + 1^2 + 1^2 + 1^2 8 = 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 , 2^2 + 2^2

위의 예시를 보면 8의 경우 8과 가장 가까운 제곱수인 4(2^2)를 8에서 뺀 4의 dp배열의 값을 활용했음을 알 수 있다. 식으로 표현하면 다음과 같은데, dp[8-4(2*2)] + 1 여기서 +1은 식에서 가까운 제곱수를 구하기 위해 빼준 값에 해당한다. 계속해서 값을 구하다보면 규칙을 찾을 수 있다. 자신의 제곱근까지의 값의 제곱수까지 탐색이 가능하고, 위의 식에 대입해가면서 가장 최소의 값을 찾으면 된다.

🤔 점화식

dp[i] = Math.min(dp[i], dp[i - j^2] + 1)

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n + 1];

        for(int i = 1; i <= n; i++) {
            dp[i] = i;
            for(int j = 1; j*j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - (j*j)] + 1);
            }
        }
        System.out.println(dp[n]);
    }
}

https://www.acmicpc.net/problem/15990

문제풀이

1, 2, 3 더하기1(9095)과 같은 문제이지만, 같은 수를 두 번 이상 연속해서 사용해서는 안된다는 조건이 있기 때문에 마지막 자리 숫자에 관한 정보를 저장해야 한다. 따라서 탐색 중인 정수 N과 마지막 자리 숫자 K의 정보를 가진 2차원 배열 DP[N][K]을 이용해 문제를 해결하였다. 예를 들어서 DP[3][1]은 정수 3을 1, 2, 3의 합으로 나타낸 방법 중 마지막이 1로 끝나는 경우의 수를 의미한다.

🤔 기본값 설정

우선 정수 N의 값이 1, 2, 3인 경우는 기존 정수들과 다르게 예외가 존재하기 때문에 따로 설정을 해줘야 한다.

• N == 1 1 -> DP[1][1] = 1
• N == 2 2 -> DP[2][2] = 1
• N == 3 2+1 -> DP[3][1] = 1 1+2 -> DP[3][2] = 1 3 -> DP[3][3] = 1

🤔 같은 수를 연속해서 사용하지 않는 법

정수 N이 4인 경우를 생각해보자. 4를 1, 2, 3의 합을 통해 만드는 경우는 세 가지가 있다.

1. DP[4-3][K] 의 경우에서 각 1을 더한 경우
2. DP[4-2][K] 의 경우에서 각 2를 더한 경우
3. DP[4-1][K] 의 경우에서 각 3을 더한 경우

• DP[4][1] - 1+2+1, 2+1+1, 3+1
• DP[4][2] - 2+2
• DP[4][3] - 1+3

이때 연속되는 수가 발생해서는 안되기 때문에 k를 더한 경우를 구할 때는 마지막 자리가 k로 끝나는 값들은 제외해야 한다.

• DP[4][1] - DP[3][1] + DP[3][2] + DP[3][3]
• DP[4][2] - DP[2][1] + DP[2][2] + DP[2][3]
• DP[4][3] - DP[1][1] + DP[1][2] + DP[1][3]

따라서 도출 가능한 점화식은 다음과 같다.

DP[i][1] = (DP[i-1][2] + DP[i-1][3]) % 1,000,000,009 DP[i][2] = (DP[i-2][1] + DP[i-2][3]) % 1,000,000,009 DP[i][3] = (DP[i-3][1] + DP[i-3][2]) % 1,000,000,009 (n >= 4)

소스코드

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

public class Main {
    static final int NUM = 1000000009;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        long[][] dp = new long[100001][4];

        dp[1][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;

        for(int i = 4; i <= 100000; i++) {
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % NUM;
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % NUM;
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % NUM;
        }

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            long answer = (dp[n][1] + dp[n][2] + dp[n][3]) % NUM;
            System.out.println(answer);
        }
        br.close();
    }
}

후기

문제를 읽고 2차원 배열과 DP를 활용해서 문제를 풀어야겠다는 판단이 들기에는 아직 부족한 듯 하다.

https://www.acmicpc.net/problem/1929

문제풀이

소수를 구하는 방법은 여러가지가 있지만, 에라토스테네스의 체를 활용하여 소수를 구하였다. 소수는 1과 자기 자신만을 약수로 갖는 수를 뜻한다. 따라서 소수가 아닌지(합성수인지)를 확인하려면 1과 자기자신 외 다른 수의 배수인지를 확인하면 된다. 결론은 에라토스테네스의 체는 소수를 찾고, 그 소수의 배수를 모두 지워나가는 방식으로 진행하면 된다.

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int M = Integer.parseInt(input[0]);
        int N = Integer.parseInt(input[1]);
        br.close();

        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        // 에라토스테네스의 체
        for(int i = 2; i < N; i++) {
            if (!isPrime[i]) continue;
            for(int j = i + i; j <= N; j += i) {
                isPrime[j] = false;
            }
        }
        // 답 출력
        for(int i = M; i <= N; i++) {
            if (isPrime[i]) System.out.println(i);
        }
    }
}

https://www.acmicpc.net/problem/11655

문제풀이

1. 입력 받은 문자열을 toCharArray()를 사용하여 char형 배열로 접근한다.
2. char형 배열의 각 문자 c가 소문자인지 대문자인지 구분한 뒤, c + 13에 해당하는 알파벳을 찾아 출력한다.

Lower case	Upper case

ASCII코드를 활용하면 쉽게 풀 수 있는 문제이다. 다만 각 문자에서 +13을 해준 값이 알파벳의 끝 'Z'혹은 'z'를 넘어가는지 확인해야 한다.

🤔 'Z' 혹은 'z'를 넘어가는 경우

c+13 이 A/a 보다 작거나 같은 경우에는 그냥 출력하면 되지만, 더 큰 경우에는 알파벳 외의 다른 문자가 적힐 수 있기 때문에 조건부 처리를 해줘야 한다.

방법은 간단한다. 넘어가는 수만큼 'A/a'에 더해주면 된다.

c = 'm(115)' --> ('c(115)' + 13) - 'z(122)' = 6 --> ('a(97)' - 1) + 6 = 'f(102)'

주의할 점은 계산에 'A/a'도 포함해야 하기 때문에 'A/a' - 1한 값에서 더해줘야 한다는 것

소스코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();

        for(char c : input.toCharArray()) {
            if (Character.isLowerCase(c)) {
                if ('z' < c + 13) bw.write(('a' - 1) + (c + 13) - 'z');
                else bw.write(c + 13);
            } else if (Character.isUpperCase(c)) {
                if ('Z' < c + 13) bw.write(('A' - 1) + (c + 13) - 'Z');
                else bw.write(c + 13);
            }
            else bw.write(c);
        }

        br.close();
        bw.flush();
    }
}

후기

쉬운 문제지만 'A/a'-1을 고려하지 못해서 오류가 생겼었다. 나중에 문자열 관련 문제 풀 때 도움이 될 것 같아서 기록해보았다.

제네릭(Generic)은 다양한 타입의 객체들을 다루는 메서드나 컬렉션 클래스에 컴파일할 때 타입 체크(compile-time type check)를 해주는 기능이다.

객체의 타입을 컴파일 시에 확인해주기 때문에 타입 안정성을 높이고 형변환이 번거로움을 줄여준다.

Generic의 필요성

굳이 Generic을 사용하지 않고 모든 타입을 받을 수 있는 Object 타입을 사용해도 되지 않을까? 다음 예제를 보면 Sample 클래스의 변수 obj는 Object타입으로 선언되어있다.

class Sample {
    private Object obj;
       public Sample(Object obj) { this.obj = obj; }
       public Object getObj() { return obj; }
}

public class Main {
    public static void main(String[] args) {
        // 객체 생성[1] > String 타입으로 생성
        Sample s1 = new Sample("안녕하세요");
        System.out.println(s1.getObj());

        // 객체 생성[2] > Integer 타입으로 생성
        Sample s2 = new Sample(100);
        System.out.println(s2.getObj());
    }
}
--------------------------------------------------------
>> 안녕하세요
>> 100

따라서 s1 객체와 s2 객체와 같이 변수 obj를 "안녕하세요"라는 문자열 타입 혹은 100의 값을 갖는 정수형 타입으로 정의하여도 객체 생성이 가능하다. 보기에는 그럴 듯해 보이지만 Object를 사용하면 다음과 같은 문제가 발생한다.

public class Main {
    public static void main(String[] args) {

            ...

            //String str = s1.getObj();      --> Error!
            //int num = s2.getObj();  --> Error!

            // 실제로는 Object 타입이기 때문에 강제 형변환이 필요하다
            String str = (String) s1.getObj();
            int num = (Integer) s2.getObj();
    }
}

보기에는 사용되는 타입(String, int)처럼 보이지만 실제로는 Object 타입이기 때문에 자동 형변환이 되지 않는다. 또한 컴파일 단계에서는 에러가 나지 않지만 실행 단계에서 Class Cast 오류가 발생하는 등 타입 안정성에 문제가 생길 수 있기 때문에 이와 같은 방법은 권장되지 않는다.

Generic 선언

제네릭은 클래스와 메서드에 선언할 수 있다. 앞서 살펴본 예제인 Sample 클래스를 활용하여 클래스에 선언해보자.

class Sample<T> {
    private T obj;
       public Sample(T obj) { this.obj = obj; }
       public T getObj() { return obj; }
}

Sample 클래스를 제네릭 클래스로 변경하고 싶다면 클래스 이름 옆에 <Type명> 을 붙이면 된다. 보통 Type의 앞글자를 따서 "T"를 많이 사용한다. 이때 T는 타입 변수(type variable)라고 한다.

이렇게 제네릭 클래스로 선언된 Sample 클래스의 객체를 생성하려면 다음과 같이 참조변수와 생성자에 타입 T대신에 실제 사용하게 될 타입을 지정해주면 된다.

public class Main {
    public static void main(String[] args) {
        // 객체 생성[1] > String
        Sample<String> s1 = new Sample<String>("안녕하세요");
        String str = s1.getObj();
        System.out.println(str);

        // 객체 생성[2] > Integer
        Sample<Integer> s2 = new Sample<Integer>(100);
        int num = s2.getObj();
        System.out.println(num);
    }
}
--------------------------------------------------------
>> 안녕하세요
>> 100

Sample 타입의 객체 s1의 경우 String 타입을 T대신에 지정해주었다. 이는 Sample< T >를 다음과 같이 지정해준 것과 같다. 이제 s1의 제네릭 타입 변수에는 String 타입의 객체만 저장 가능하다.

class Sample<String> {
    private String obj;
       public Sample(String obj) { this.obj = obj; }
       public String getObj() { return obj; }
}

만약에 타입을 지정해주지 않고 그냥 사용하게 된다면 Object형으로 간주된다. 이렇게도 사용은 가능하지만 안전하지 않다는 경고가 발생한다.

Generic의 제한

❌ static 멤버에는 적용할 수 없다.

이처럼 제네릭 클래스의 객체를 생성할 때는 객체 별로 다른 타입을 지정하는 것이 가능하다. 그러나 모든 객체에 동일하게 동작해야 하는 static 멤버에는 타입 변수를 적용할 수 없다. static 멤버는 지정된 타입 변수와 관계 없이 동일한 것이어야 하기 때문이다.

❌ 배열을 생성할 수 없다.

제네릭 배열 타입의 참조 변수를 선언하는 것은 가능하다. 하지만 'new T[ ]'와 같이 배열을 선언하는 것은 불가능하다.

_(꼭 제네릭 배열을 생성해야 한다면 'Reflection API'의 newInstance()와 같이 동적으로 생성하는 메서드의 배열을 생성하거나, Object 배열을 생성한 뒤 T[ ]로 형변환하는 방법 등이 있다) _

다형성은 다양한 형태 또는 특성을 갖는다는 의미이다. Java 객체 지향 프로그래밍에서는 부모클래스를 상속 받는 자식클래스의 인스턴스가 부모의 객체로도 사용되고, 자식클래스의 객체로도 사용될 수 있는 다양한 상황을 의미한다.

🤔 다형성을 활용한 객체 생성 방법?

다형성은 상속(extends)을 통해서 구현이 가능하다. 아래 코드를 보면 부모클래스 Bird가 있고, 이를 상속 받는 자식클래스 Parrot이 있다.

class Bird {
    String name = "새";
    void method1() { System.out.printf("%s이다.%n", name); }
    void bird_method() { System.out.println("부모 클래스 Bird"); }
}

class Parrot extends Bird {
    String name = "앵무새";
    String bird_name = "앵무새";
    void parrot_method() { System.out.println("자식 클래스 Parrot"); }

    @Override
    void method1() {
        System.out.println(System.out.printf("새의 종류는 %s이다.%n", bird_name));
    }
}

두 클래스를 활용하여 네 가지 방법으로 객체를 생성해보자.

객체 생성 [1] : 부모 + 자식 클래스의 모든 자원 사용 가능

Parrot 타입의 객체 parrot1은 너무나 당연하게도 상속 받은 부모클래스의 자원과 본인(자식클래스)의 자원 모두 이용이 가능하다.

Parrot parrot1 = new Parrot();

Parrot parrot1 = new Parrot();
System.out.println(parrot1.name);
System.out.println(parrot1.bird_name);
parrot1.method1();
parrot1.parrot_method();
parrot1.bird_method();
-----------------------------------------
>> 앵무새
>> 앵무새
>> 새의 종류는 앵무새이다.
>> 자식 클래스 Parrot
>> 부모 클래스 Bird

이때 상속 받은 메서드 method1과 String 변수 name의 경우 자식클래스에서 오버라이드한 형태로 출력되는 것을 알 수 있다. 그렇다면 Parrot클래스에서는 method1의 원본 "새이다."를 출력할 수 없는 걸까?

🤔 만약 자식클래스에서 오버라이드된 부모클래스의 원본 자원을 호출하고 싶다면? ---> super 키워드 사용

super 키워드를 사용하면 자식클래스에서도 원본 메서드의 이용이 가능하다.

class Bird {
    String name = "새";
    void method1() { System.out.printf("%s이다.%n", this.name); }
    ...
}

class Parrot extends Bird {
    ...
    void method2() {
        super.method1();
        System.out.println(super.name);
    }
}
public class Main {
    public static void main(String[] args) {
        Parrot parrot = new Parrot();
        parrot1.method2();
    }
}
-----------------------------------------------------------------
>> 새이다.
>> 새 

Parrot클래스에 부모클래스 Bird의 메서드 method1과 변수 name을 super키워드로 받은 후, 이들을 출력하는 메서드 method2를 만들어주었다. super 키워드로 받은 값은 부모클래스의 원본 값 그대로 출력됨을 확인할 수 있다.

객체 생성 [2] : 부모클래스의 모든 자원 사용 가능

너무나 당연하게도 Bird 타입의 객체 bird1도 Bird클래스의 자원을 이용할 수 있다. 그리고 또 너무나 당연하게도 자식 클래스의 자원은 이용할 수 없다.

Bird bird1 = new Bird();

Bird bird1 = new Bird();
System.out.println(bird1.name);
bird1.method1();
bird1.bird_method();
------------------------------------
>> 새
>> 새이다.
>> 부모 클래스 Bird

객체 생성 [3] : 부모클래스의 자원만 사용 가능?

그렇다면 타입은 부모클래스(Bird)이되, 자식클래스(Parrot)로 bird2객체를 생성해보자. bird2의 타입이 부모클래스이기 때문에 부모클래스, Bird의 자원은 사용이 가능하다.

Bird bird2 = new Parrot();

Bird bird2 = new Parrot();
System.out.println(bird2.name);
// System.out.println(bird2.bird_name); >> Error! 자식클래스의 자원 사용 못함
bird2.method1();
bird2.bird_method();
// bird2.parrot_method();               >> Error! 자식클래스의 자원 사용 못함
------------------------------------
>> 새
>> 새의 종류는 앵무새이다.
>> 부모 클래스 Bird

여기서 두 가지 흥미로운 점을 볼 수 있다.

• 자식 클래스의 자원은 이용할 수 없다.
• 상속 받는 메서드의 경우 자식클래스의 것을 실행된다.

정말 부모클래스 타입 + 자식클래스로 생성 의 경우에는 오버라이드된 자식클래스의 메서드외에는 부모클래스의 자원만 사용 가능한 것일까?

🤔 만약 자식클래스의 자원을 사용하고 싶다면? ---> 형 변환!

bird2의 타입을 자식클래스(Parrot)로 강제 형 변환을 하면 자식클래스의 자원에도 접근이 가능하다!

((Parrot)bird2).parrot_method();
System.out.println(((Parrot) bird2).bird_name);
------------------------------------------------
>> 자식 클래스 Parrot
>> 앵무새

객체 생성 [4] : 부모클래스 객체 생성시 자식 타입으로 생성 불가!

앞서 본 객체 생성 방식[3]과 반대로 자식클래스 타입 + 부모클래스로 생성은 불가능하다.

Parrot parrot2 = new Bird(); >> Error!

정리

정리하면, 하위클래스의 인스턴스(객체)는 상위클래스의 인스턴스로도 사용될 수 있다. 하지만 반대로 성립될 수 없다. 왜냐하면 앵무새(Parrot class)는 그 상위인 새(Bird class)라고 말할 수 있지만, 모든 새가 앵무새는 아니기 때문이다! 따라서 상위(부모)클래스의 인스턴스는 하위(자식)클래스의 인스턴스로 사용될 수 없다.

인터페이스란 사용자 또는 컴퓨터 간의 통신이 가능하도록 해주는 디바이스 프로그램을 의미한다. 쉽게 말해서 하나의 표준화를 제공하는 중간 매개체를 뜻한다.

Java에서의 인터페이스는 다른 클래스를 작성할 때 기본이 되는 틀을 제공하고, 다른 클래스 사이의 중간 매개 역할까지 담당하는 일종의 추상 클래스이다.

인터페이스가 기능에 대한 선언을 제공하면 인터페이스를 구현하는 클래스에서는 추상화된 기능을 구현한다.

🤔 인터페이스 어떻게 사용하지?

Java에서 인터페이스는 인터페이스 명 앞에 interface 키워드를 붙여 사용이 가능하다. 그리고 클래스는 클래스명 뒤에 implements 키워드 + 인터페이스명을 입력하여 해당 인터페이스를 구현하고자 함을 선언할 수 있다. 그렇게 어떤 클래스가 인터페이스를 사용(상속)한다면 인터페이스에 선언되어져 있는 메서드를 구현해야 한다. 추상 클래스와 같이 인터페이스에는 메서드의 구체적인 내용이 기술되어 있지 않기 때문에 상속 받은 클래스에서 재정의(오버라이딩)하여 메서드를 이용할 수 있다.

interface Allowance {
    int monthly_allowance = 30000;

    void in(int value, String name);
    void out(int value, String name);
}

interface Academy {
    void pay(int academy_fee, String name);
}

Allowance 인터페이스는 용돈의 입출금 기능을 선언하고, Academy 인터페이스는 학원비 결제 기능을 선언한다고 해보자.

class Student implements Allowance, Academy {
    // 인터페이스 구현
    @Override
    public void in(int value, String name) {
        System.out.printf("%s에게서 %d원 용돈을 받았습니다.%n", name, value);
    }

    @Override
    public void out(int value, String name) {
        System.out.printf("금액 %d원을 %s(으)로 지출했습니다.%n", value, name);
    }

    @Override
    public void pay(int academy_fee, String name) {
        System.out.printf("%s 학원비 %d 입금 완료.%n", name, academy_fee);
    }
}

Student 클래스는 위의 두 인터페이스를 구현한다. implements 키워드를 이용해 인터페이스를 구현하겠음을 선언해준 뒤, 콤마(,)를 이용해 인터페이스를 다중 상속할 수 있다. Student 클래스에서 인터페이스의 추상 메서드를 오버라이딩하여 기능을 구체화한다.

public class Main {
    public static void main(String[] args) {
        Student s1 = new Student();

        s1.in(5000, "엄마");
        s1.out(2000, "PC방");
        s1.in(s1.monthly_allowance, "엄마");
        s1.pay(300000, "수학 학원");

        System.out.println(Allowance.monthly_allowance);
    }
}
------------------------------------------------------------
>> 엄마에게서 5000원 용돈을 받았습니다.
>> 금액 2000원을 PC방(으)로 지출했습니다.
>> 엄마에게서 30000원 용돈을 받았습니다.
>> 수학 학원 학원비 300000 입금 완료.
>> 30000

🤔 장점(왜 써야 하는가)

인터페이스를 이용하면 메서드의 추상적인 선언과 그 메서드들을 구체적으로 구현한 부분을 분리할 수 있다. 이렇게 인터페이스를 통해 분업화된 시스템을 구축하여 개발 주체마다 독립적으로 프로젝트를 개발할 수 있다.

인터페이스 VS 추상클래스

https://techvidvan.com/tutorials/abstract-class-vs-interface/

- 사용방법

상속을 받기 위해서 추상클래스는 extends 키워드를 사용하고, 인터페이스는 implements 키워드를 사용한다.

- 메서드 타입

추상클래스는 추상메서드, 일반 메서드 모두 가질 수 있다. 반면에 인터페이스는 추상메서드만을 갖는다. *Java8부터는 default메서드와 static메서드도 가질 수 있게 되었다.

- 상수(Final Variables)

인터페이스에 선언된 변수는 기본적으로 final 변수, 즉 상수이다. 추상클래스는 non-final 변수까지 포함 가능하다.

- 변수 타입

인터페이스는 오직 static 변수와 final 변수만을 갖는다. 반면에 추상 클래스는 final, non-final / static, non-static 변수 모두를 가질 수 있다.

- 구현

추상클래스는 인터페이스의 구현을 제공할 수 있으나, 반대로 인터페이스는 추상클래스를 구현할 수 없다.

- 상속

인터페이스는 오직 다른 인터페이스만을 상속할 수 있다. 추상클래스는 다른 클래스도 상속 가능하며 다중 인터페이스 구현도 가능하다.

- 데이터 변수 접근성

인터페이스 변수는 기본적으로 public이다. 추상클래스 변수는 private, protected 등 모든 접근 제어자를 가질 수 있다.

https://www.geeksforgeeks.org/difference-between-abstract-class-and-interface-in-java/

- 다중 상속 기능 제공

인터페이스의 역할과 구현은 앞서 살펴본 추상 클래스와 상당히 유사하다. 그러나 클래스를 다중 상속할 경우 메소드 출처의 모호성 등 여러 문제가 발생할 가능성이 있기 때문에 Java에서는 클래스를 이용한 다중 상속을 지원하고 있지 않다. 하지만 다중 상속의 이점도 있기 때문에 인터페이스를 이용해 다중 상속 기능을 제공하고 있다.

- 우선순위(extends VS implements)

상속을 받는 extends 키워드와 구현을 받는 implements 키워드를 동시에 사용하면 extends 키워드가 먼저 사용되어야 한다.

class Student extends Person implements Allowance, Academy {...}

추상 클래스는 구체적인 내용은 작성하지 않고, 공통적인 특징을 추상적으로 선언한 클래스이다.

여기서 공통적인 특징은 필드나 메서드가 될 수 있는데, 메서드의 경우 리턴값조차 갖지 않고 메서드명만 선언될 뿐이다.

추상 클래스와 추상 메서드의 선언은 클래스 앞에 abstract 키워드를 붙이면 된다.

abstract class Animal {
    abstract void cry();
}

아무래도 구체적인 내용이 없기 때문에 추상 클래스만으로는 객체를 생성할 수가 없다. 따라서 추상 클래스를 활용하기 위해서는 추상 클래스에 대한 구체적인 설명이 필요하다!

Animal animal = new Animal(); // Error!

🤔 추상 클래스 사용 방법

구체적인 설명을 어떻게 정의할 수 있을까? > 바로 상속이다. 추상 클래스를 상속받는 자식 클래스에서 해당 추상 메서드를 오버라이드(Override)하여 재정의한다면 추상 클래스 활용이 가능하다. 예제를 통해 살펴보자.

우선 앞에서 등장했던 Animal이라는 이름의 추상 클래스를 다음과 같이 선언하였다.

abstract class Animal {
    String kind;
    void common() {
        System.out.println("동물이다");
    }
    abstract void cry();
}

구성을 보면 일반 변수와 함수, 그리고 추상 메서드를 가지고 있다. 사실 추상 클래스는 abstract를 앞에 붙이고 클래스 안에 추상 메서드를 포함하고 있다는 것을 제외하면 사실상 일반 클래스와 별반 차이 없다. Field, Constructor, Method(추상메서드가 아닌 일반 메서드) 모두 포함 가능하다.

class Dog extends Animal {
    public Dog() {
        this.kind = "포유류";
    }

    @Override
    void cry() { System.out.println("멍멍"); }
}

Animal 클래스를 구현한 (상속 받은) Dog 클래스이다. 이때 변수 kind와 메서드 commom()은 정의할 필요 없지만, 추상 메서드 cry()를 오버라이드하여 재정의하지 않으면 오류가 난다.

Dog dog = new Dog();
dog.common();
dog.cry();
System.out.println(dog.kind);
---------------------------------------------
>> 동물이다
>> 멍멍
>> 포유류

그 외 다양한 활용 예제

class Crow extends Animal {
    public Crow() {
        this.kind = "조류";
    }

    @Override
    void cry() { System.out.println("깍"); }
}

Animal cat = new Animal() {
    @Override
    void cry() {
        System.out.println("야옹");
    }
};
cat.cry();

Animal poodle = new Dog(); // 자동 형변환
poodle.cry();
-----------------------------------------------
>> 멍멍

이렇듯 추상 클래스는 부모 클래스의 역할을 수행한다. 하지만 구체적인 사용은 자식 클래스에서의 재정의를 통해서만 가능하다는 강제성을 띄고 있다. 덕분에 추상 클래스에서 선언만 해놓음으로써 새로운 클래스를 작성할 때마다 하나의 틀을 제공한다.

🤔 추상 클래스의 기능, 추상 클래스는 왜 필요한 것인가

왜 이렇게까지 해야 하는지 궁금할 것이다. 간단히 말하면 강제하기 위함이다. 부모(추상)클래스가 선언해놓은 메서드를 상속 받은 자식 클래스들이 이름 그대로 재정의해서 구현하라고 제한을 두는 것이다. 상속 받은 자식 클래스 입장에서는 자칫하면 상속만 받고 재정의해서 사용을 안할 수도 있다. 따라서 활용성을 높이기 위해 상속 받은 자식 클래스 입장에서는 추상메서드를 재정의해서 구현하도록 하는 것이다. 만약 자식 클래스에서 상속 받은 추상 메서드를 구현하고 싶지 않다면 자식 클래스도 앞에 abstract를 붙여 추상 클래스로 만들면 된다.

정리 및 결론

• 추상 클래스는 다른 (자식)클래스들의 공통적인 특징을 변수나 메서드로 정의해 놓는 것을 말함 -> 추상메서드

• 메서드 선언만 있고 구체적인 내용 없음 -> 객체 생성 불가능 !

• 부모 클래스로서의 역할 O, 하지만 구체적인 사용은 자식 클래스에서 재정의하야여 가능(강제성)

부모(추상) 클래스에서 구현 하지 않는 이유는 해당 메서드의 구현이 상속 받는 클래스에 따라서 달라질 수 있기 때문에 선언만 해둔 것이다. 덕분에 추상 클래스는 여러 명의 개발자가 작업할 때 코드의 확장과 분업을 효율적으로 처리할 수 있게 해준다. 따라서 분업화된 시스템에서 공통의 프로젝트를 진행할 때 많이 사용되어지는 중요한 문법이다!

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예제

progresses | speeds | return | |:----------:|:----------:|:----------:| | [93, 30, 55] | [1, 30, 5] | [2, 1] | | [95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |

https://programmers.co.kr/learn/courses/30/lessons/42586

문제풀이

프로그래머스 상에서는 Stack/Queue 자료구조를 활용하여 풀이하는 것으로 나와있지만 큐로 풀려고 시도하다가 화병나서 그만두고 결국 배열로 푸는 방법을 찾아서 풀었다. 배포까지 필요한 일수를 구하고, 이를 활용하여 풀 수 있는 간단한 방법이다. 문제의 핵심은 개발 진도가 100%가 될 때까지 걸리는 시간과 앞의 기능이 배포되었는지를 확인하는 것이라고 생각했다.

🤔 100%가 될 때까지 걸리는 시간

현재까지 진행된 진도의 정도(progressses)와 기능마다 걸리는 개발 속도(speeds)가 있다면 개발 진도가 100%가 될 때까지 걸리는 시간(일수)는 쉽게 구할 수 있다.

기능[i]의 개발 진도가 100%가 될 때까지 걸리는 시간 = (100 - progresses[i]) / speeds[i]

이때 2.5 등의 값이 나올 수 있으므로 올림 처리가 필요하다. 이때 double형 값이 나와야 올림 처리가 제대로 동작할 수 있기 때문에 분모가 int형으로 자동 변환되지 않게 신경 써주는 것이 필요하다. 구해진 값은 days라는 이름의 int형 배열에 작업 순서대로 넣어주었다.

days[i] = (int) Math.ceil((100 - progresses[i]) / (double)speeds[i])

🤔 각 날마다 배포된 기능의 수 구하기

작업 완료(100%) 외에 기능이 배포되기 위한 조건이 하나 더 있다. 앞의 기능이 먼저 완료되어야 한다는 것이다. 입력 예제를 통해 구한 days 배열은 다음과 같다 > [7, 3, 10] 2번째 작업이 3일 후에 가장 먼저 완료가 되었지만, 1번 작업이 아직 완료되지 않았으므로 배포될 수 없다. 따라서 1번 작업이 완료된 7일째 되는 날에 처음으로 두 개의 작업이 배포된다. 그런 다음 3일이 지난 후 마지막 3번째 작업이 배포된다. > return [2, 1]

이와 같은 과정을 구현하기 위해서 두 개의 변수를 만들었다. 가장 앞 순서의 기능의 작업이 완료하기 까지의 시간값을 갖는 정수형 변수 time, 그리고 배포 가능한 기능의 개수를 나타내는 정수형 변수 count 이다.

우선 1번째 작업이 완료하기 까지의 시간을 time으로 설정해주고, 1번째 작업이 우서적으로 배포 가능해야 하기 때문에 count를 1로 설정하였다. 그런 다음 두 번째 작업부터 마지막까지 새로 time과 count를 설정하는 과정을 반복한다. 이때 두 가지 경우가 있다.

1. 현재 설정된 time 보다 [i]작업의 작업기간이 더 긴 경우 이는 아직 작업이 완료되지 않은 것이다. 일단 현재까지의 count 값을 answer리스트에 넣고 time을 [i]작업의 작업기간으로 설정하고, count를 1로 초기화한 뒤 반복문을 계속한다.

2. 현재 설정된 time 보다 [i]작업의 작업기간이 더 작은 경우 이미 작업은 완료되었고, 앞의 작업이 완료되기를 기다리고 있는 경우이다. 배포 가능한 기능의 개수를 나타내는 count변수를 +1한다.

마지막으로 반복문이 다 돌면 현재까지의 count를 answer에 추가하여 코드를 마무리한다.

소스코드

import java.util.*;

class Solution {
    public List<Integer> solution(int[] progresses, int[] speeds) {
        List<Integer> answer = new ArrayList<>();
        int[] days = new int[progresses.length];
        for(int i = 0; i < progresses.length; i++)
            days[i] = (int)Math.ceil((100 - progresses[i]) / (double)speeds[i]);

        int time = days[0];
        int count = 1;
        for(int i = 1; i < days.length; i++) {
            if (time < days[i]) {
                answer.add(count);
                time = days[i];
                count = 1;
            } else count++;
        }
        answer.add(count);
        return answer;
    }
}

후기

역시 머리가 비상해야 쉽게 풀 수 있나보다. 왜 작업정도와 작업까지 걸리는 시간을 쥐어주었는데도 이를 활용하지 못했을까. 문제 풀이 방법을 고안해내는 과정은 아직 멀었다.

https://www.acmicpc.net/problem/1107

문제풀이

브루트포스 알고리즘으로 풀 수 있는 문제이다. 우선 생각해볼 수 있는 채널 이동 방법은 다음이 있다.

1) 숫자(0-9)버튼을 통해 목표 채널에 도달
2) +/- 버튼을 통해 목표 채널에 도달
3) 숫자 버튼을 이용해 목표 채널에 가까운 채널로 이동 후, +/- 버튼 통해 목표 채널에 도달

🤔 채널 이동 방법을 어떻게 구현할까

우선 출력해줄 값인 result 변수를 초기화해주자. 가장 간단하게 구현할 수 있는 방법은 2번(+/-버튼)이다.

int result = Math.abs(N - 100)

+/- 버튼은 각 +1/-1씩 이동한다. 따라서 목표값에서 현재 위치한 값을 빼주면 +/- 버튼 눌러야 하는 횟수를 알 수 있다. 이때 목표 채널이 현재 채널(100번)보다 작을 수 있으므로 절대값으로 변환해주는 것을 잊지 말자.

다음은 숫자 버튼을 이용하여 목표 채널에 도달하는 방법을 구현해보자. 목표 채널의 최댓값은 500,000 이지만 실제로 버튼은 0부터 9까지 존재하기 때문에 누를 수 있는 채널은 999,999까지 있다. 우리의 문제 풀이 접근 방식은 브루트포스이기 때문에 모든 경우를 고려해 줘야 한다. 완전탐색답게 0부터 999,999까지 반복문을 반복하여 탐색한다.

🤔 고장난 버튼과 가까운 채널을 찾는 방법

모든 숫자 버튼을 탐색하면서 동시에 3번 방법(가까운 채널 탐색 후, +/- 버튼으로 목표 채널 도달)도 구현해보자.

먼저 현재 탐색 중인 채널을 String 변수로 받아서 임시로 정의한다. 그리고 중간에 반복문을 빠져나가야 하는지 판단할 boolean형 변수 isBreak도 선언해준다. 우리는 모든 채널을 탐색하면서 다음을 확인해야 한다.

1) 현재 탐색 중인 채널에 고장난 숫자 버튼이 포함되어 있는 경우
2) 현재 탐색 중인 채널로 이동 가능한 경우(고장난 버튼이 없음)

만약 전자와 같다면 우리는 해당 채널로 이동할 수 없기 때문에 isBreak를 true 값으로 변환하고 반복문을 빠져나와 다음의 채널을 탐색해야 한다.

후자라면 현재 탐색 중인 채널이 목표 채널과 가까운 채널임을 확인하고 결과를 설정해야 한다. 방법은 임의의 변수 min에 현재 탐색 중인 채널로 이동하기 위해 눌러야 하는 횟수를 저장해주고, 미리 선언된 result 변수와 비교하여 둘 중 최솟값으로 result 값을 변경해주면 된다.

• 임의 변수 min 설정(현재 탐색 중인 채널로 이동하기 위해 버튼을 누르는 횟수)

  int min = len + Math.abs(N - i)

len은 현재 탐색 중인 채널의 길이로 만약 두 자릿수라면 두 번 눌러줘야 한다는 것을 의미한다. 그런 다음 +/-로 목표 채널에 도달하기 위해 버튼을 눌러줘야 하기 때문에 다음과 같은 식이 성립된다.

• 미리 선언된 result값과 비교, 둘 중 더 작은 값으로 result 변수 변경

  result = Math.min(result, min)

Math클래스의 min함수를 이용해 현재 채널에서의 이동 횟수와 result로 저장된 이동 횟수 중 더 작은 값으로 result 변수를 업데이트해준다.

0부터 999,999까지 위의 과정을 반복해가며 result값을 업데이트해주는 것이다.

소스코드

public class BOJ1107 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        boolean[] broken = new boolean[10];
        // 고장난 버튼이 0개일 경우 입력 skip 처리 -> NP 방지
        if (M != 0) {
            String[] input = br.readLine().split(" ");
            for(int i = 0; i < M; i++)
                broken[Integer.parseInt(input[i])] = true;
        }
        br.close();

        int result = Math.abs(N - 100); // 2번 방법으로 초기화
        // 고장나지 않은 리모콘 버튼으로만 N과 가장 근사한 번호를 만든 후 +, - 로 이동하는 값 중의 최소값을 선택
        for(int i = 0; i <= 999999; i++) {
            String str = String.valueOf(i);
            int len = str.length();
            boolean isBreak = false;

            for(int j = 0; j < len; j++) {
                if(broken[str.charAt(j) - '0']) {
                    isBreak = true;
                    break;
                }
            }
            if(!isBreak) {
                int min = len + Math.abs(N - i);
                result = Math.min(min, result);
            }
        }
        System.out.println(result);
    }
}

후기

가장 간단하고 무식한 방법이지만 브루트포스 알고리즘 문제는 많이 풀어보지 않아서 접근 방법을 모색하기가 어려웠다. 최대값인 500,000에 속아서 999,999까지 탐색하는 것을 놓치냐 안 놓치냐가 풀이의 관건인 듯 하다. 그 뒤에도 고장난 채널을 처리하는 방법, 현재 탐색 중인 채널의 길이까지 고려하여 이동 횟수를 구하는 법 등 고려사항들이 많은 문제였다. 괜히 골드가 아니다... 언제쯤 세세한 조건들을 꼼꼼하게 챙기며 구현할 수 있을까!

https://www.acmicpc.net/problem/16947

문제 풀이

그래프 탐색을 통해 풀 수 있는 문제이다. 문제 접근 방식은 다음과 같다.

1. DFS 통해 순환선에 해당하는 역 탐색
2. BFS 통해 순환선과의 거리 확인

🤔 순환선임을 알 수 있는 방법?

우선 역과 역의 연결 관계를 나타내는 인접리스트를 생성한다. 그리고 깊이 우선 탐색 방법으로 현재 역(now)과 연결된 역을 탐색한다. 다음으로 탐색할 역의 경우의 수는 다음과 같다.

✔️ 이전에 방문한 역이 아니면서 방문한 적이 있는 역일 경우
✔️ 아직 방문하지 않은 역일 경우

📎 visited[next] && next != pre

첫 번째 케이스는 곧 순환선임을 의미한다. 1 > 2 > 3 > 1 순환선의 경우 3에서 다시 1을 탐색하는 경우가 이에 해당한다. 이전에 방문한 역이 아님을 표시해줘야 하는 이유는 인접 리스트 특성 상 이전에 방문한 역을 다시 탐색하게 되기 때문이다. 이때 방문표시가 돼있다는 이유만으로 순환선이라고 단언해버리면 안된다! 방금 방문한 역과 현재 방문한 역 둘 사이의 관계는 연결 관계일 뿐, 순환선은 아니기 때문이다.

ex) 1 > 2 > 1 - 순환선이 아님!

그럼 순환선이기 때문에 순환선 여부를 의미하는 변수를 참으로 표시해주고, 현재 탐색 역과 순환선과의 거리를 0으로 설정해주자. 그리고 후에 순환선과 역과의 거리를 BFS 로 계산할 것이기 때문에 미리 선언해둔 Queue에 순환선으로 판단된 역(next)을 넣어준다.

📎 !visited[next]

두 번째 케이스의 경우 아직 순환선을 찾지 못했기 때문에 계속 깊이 우선 탐색을 진행한다. 깊이 우선 탐색을 통해 순환선을 발견하면 이제 isCycle 변수를 참으로 표시하여 순환선의 존재여부를 나타내준다. 만약 순환선이 존재한다면 지금까지 순환선에 해당하는 역들의 거리를 0으로 설정하여 거리 계산과 함께 순환선에 해당하는 역을 표시할 수 있다.

🤔 각 역과 순환선과의 거리?

거리를 구하는 방식은 DFS, BFS 둘 중 하나를 사용해도 상관없다. 나는 최소 거리를 구해주는 방식이라서 습관적으로 BFS를 택했다.

1. Queue들어있는 순환역들을 탐색한다.
2. 각 순환역과 연결된 다른 역들을 탐색한다. 2-1) 이때 위의 순환역과 연결된 역을 탐색하는 과정에서 이미 거리가 구해진 것들은 제외 2-2) 거리가 아직 구해지지 않았다면(-1) 현재 거리값(변수cnt)을 거리값으로 설정한 뒤, 현재 탐색 중인 연결된 역을 큐에 삽입
3. 큐 삽입 전 들어있던 역들의 탐색이 완료되면 거리값 증가

위 과정을 큐가 비워질 때까지 반복하면 순환선과 다른 역과의 거리가 구해진다. 이때 거리값은 그래프에서 트리구조의 레벨이라고 생각하면 된다.

소스 코드

public class Main {
    private static int N;
    private static boolean[] visited;
    private static int[] distance;
    private static boolean isCycle;
    private static Queue<Integer> queue = new LinkedList<>();

    private static void dfs(ArrayList<Integer>[] graph, int pre, int now) {
        visited[now] = true;
        for(int next : graph[now]) {
            // next가 직전 방문지가 아니면서 이미 방문한 적 있음 -> 순환선
            if (visited[next] && next != pre) {
                isCycle = true;
                distance[next] = 0;
                queue.offer(next);
                break;

            // 아직 방문하지 않은 역 탐색
            } else if (!visited[next]) {
                dfs(graph, now, next);
                // 탐색한 역이 순환역일 경우
                if(isCycle) {
                    if(distance[next] == 0) {
                        isCycle = false;
                    } else {
                        distance[next] = 0;
                        queue.offer(next);
                    }
                    return;
                }
            }
        }
    }

    private static void bfs(ArrayList<Integer>[] graph) {
        int cnt = 1;
        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int j = 0; j < len; j++) {
                int tmp = queue.poll();
                // 연결된 구간을 다음 탐색지에 추가
                for (int i : graph[tmp]) {
                    // 거리가 이미 구해진 역은 제외
                    if (distance[i] != -1) continue;
                    distance[i] = cnt;
                    queue.add(i);
                }
            }
            cnt++; // 순환선과의 거리
        }
    }

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

        visited = new boolean[N + 1];
        distance = new int[N + 1];
        Arrays.fill(distance, -1);
        // 연결 구간 정보 입력
        ArrayList<Integer> graph[] = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            graph[a].add(b);
            graph[b].add(a);
        }
        // 그래프에서 순환선 찾기
        dfs(graph, 0, 1);
        // 역과 순환선의 거리 구하기
        bfs(graph);
        for(int i = 1; i <= N; i++) {
            System.out.print(distance[i] + " ");
        }
    }
}

후기

역시 골드 랭크답게 두 가지 알고리즘을 활용해야 했다. 순환선을 구하는 방법에서 힌트를 얻고 나서야 문제를 풀 수 있었다. 순환선을 탐색하는 문제 유형은 이 문제말고도 다른 문제에서도 다양한 형태로 등장할 수 있으니 잘 외워 둬야겠다.