Record for Success

| 퍼셉트론이 뭘까?

대학교에서 인공지능개론 수업을 들을 때, 퍼셉트론을 뉴런이라고 했다가, 알고리즘이라고 했다가 이런 식으로 설명하시는걸 그대로 필기해서 나중에 정말 헷갈렸던 경험이 있다.

퍼셉트론은 Input(x)에서부터 weight(w)를 바탕으로 계산된 output(y_hat)을 도출하는 일련의 수학적인 과정 전체를 의미한다.

이 연산 과정은 인간 뇌 속에 있는 뉴런의 동작 방식과 유사하기 때문에 artificial neuron이라고도 한다고..

(뇌의 뉴런도 시냅스에 입력된 정보를 전기신호(출력형태)로 축삭돌기를 통해 보내는 어쩌구..)

이런 저런 아티클들을 찾아보니, 뉴런과 퍼셉트론에 대한 이해는 아래와 같이 여러 갈래로 정리하고 있었다.

1. 퍼셉트론과 뉴런의 차이는 artifical 이냐 biological 이냐로 본다.

2. 퍼셉트론은 딥러닝 동작 방식의 기초가 되는 인풋->아웃풋의 일련의 과정이며,

    인풋과 아웃풋 그 사이 중간의 연산을 통해 활성화 되는 하나의 셀을 뉴런이라고 한다.

### Whole step = perceptron

def call_me_perceptron(input=None):
    # 1.inputs
    if not input:
    	input = np.array([1, 2, 3])

    # 2.weights
    w = np.array([.5, .5, .5])

    # 3.bias 
    bias = -.7

    # 4.calculate output
    output = np.sum(w*input)+b
    
    return output

SLP (Single Layer Perceptron) 는 그림과 똑같기 때문에 뉴런? 이랑 아웃풋이랑 무슨 차이지.. 하는 느낌이 강하게 들지만, MLP (Multiple Layer Perceptron) 에서는 확실히 여러 레이어가 존재하기 때문에 뉴런의 존재를 더욱 뚜렷하게 느낄 수 있다.

SLP, 즉 하나(한번?)의 퍼셉트론으로는 XOR (두 입력 값의 이진 분류가 다르면 1, 같으면 0 반환) 의 문제: 선형으로 풀 수 없는 복잡한 문제는 풀 수 없기에, MLP의 개념이 등장했고 이것이 딥러닝 발전을 이끌기 시작했다.

SLP는 위에 작성한 간단한 코드처럼 복잡한 라이브러리 연산 없이도 구현할 수 있으므로 코드는 생략한다.

※참고: 파이썬으로 시작하는 머신러닝+딥러닝

인공지능(AI, Artificial Intelligence)이란, 기계가 사람의 학습 형태를 모방하여 지능을 가진 것 처럼 행동하도록 만든 것을 의미한다.

최근 해당 분야가 각광받기 시작하면서 머신러닝, 딥러닝 등의 용어를 쉽게 접할 수 있는데 결국은 AI안에 포함된 개념이다.

머신러닝은 인공지능 객체가 데이터에 대한 규칙 또는 정보를 학습할 수 있도록 설계하는 알고리즘이며, 딥러닝은 이런 머신러닝 기법의 일종으로 신경망 알고리즘을 적용해 인간과 유사하게 판단하는 프로그램을 구현한 기계 학습 방법이다.

인공지능이라는 개념이 등장한건 17~18세기 경이고, 직접 구현되기 시작한건 컴퓨터가 등장한 후 1900년대 중반부터이지만, 정보 처리 방법과 당시 컴퓨터의 성능의 한계로 크게 발전하지 못했다.

그러다 파라미터의 학습 과정을 역으로 전파하며 파라미터 값을 조정하는 역전파(Backpropagation) 알고리즘과 퍼셉트론(Perceptron)이 등장하면서 딥러닝 기반의 인공지능 개념이 성장하기 시작했다.

딥러닝에 대한 간단한 소개

딥러닝 모델은 단순한 퍼셉트론의 배치와 순전파 과정으로만 학습되는 것이 아닌, 상기 사진에서 확인할 수 있는 것 처럼 여러 개의 퍼셉트론과 여러 은닉층(Hidden Layer)를 추가함으로써 복잡한 데이터에서 학습하고 문제를 해결할 수 있다.

은닉층(Hidden Layer)란, 인풋에서 특정 계산식을 통해 도출된 결과를 임시로 저장하는 층으로 생각할 수 있고,

특정 계산식은 구현하고자 하는 모델에 따라 달라질 수 있고, 계산식에 포함된 파라미터값을 조정하여 가장 정답 레이블과 가까운 답을 찾아가는 과정이 딥러닝 학습 과정이라고 볼 수 있다.

계산식에 포함된 파라미터값을 조정하는 과정은 앞서 언급했던 역전파 알고리즘을 통해 Loss 값이 최소가 되도록 찾아가는 과정이다.

다양한 딥러닝 모델들의 가장 기초적인 부분부터 공부를 하고 블로그에 기재하고 있으며, 최종 목표인 멀티모달까지의 과정을 최대한 자세히 이해할 수 있도록 노력할 예정이다.

문제 출처: 프로그래머스

문제 설명

🔎 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

설명의 길이가 길어 문제 이해에 도움이 되는 일부만 발췌하였습니다. 상세한 내용은 프로그래머스 페이지에서 확인하실 수 있습니다.

내 기준에서 이 문제는 문제를 정확히 파악하는 것이 해결의 관건이었다.

처음에는 문자열 내부에 있는 중복되는 문자열로 압축했을 때 가장 짧은 길이가 나오면 되는 줄 알았다.

(ex. 'abbbccc' ➡'a3b3c')

하지만, 마지막 예시에 '문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.'  이라는 문구가 있는데 이를 기준으로 'abbbccc'를 다시 3개씩 자르면 'abb, bcc, c'가 되므로 자를 수 없다.

아래 사진은 "xababcdcdababcdcd" 를 압축하는 법에 대해 설명한다.

이를 이해한 후 문제를 푸니 간단하게 풀렸다.

<정답 코드>

def solution(s):
    n = len(s)
    answer = n
    
    for i in range(1, n//2+1):
        before = s[:i]
        same = 1
        new = ''
        for j in range(i, n, i):
            temp = s[j:j+i]
            if before == temp:
                same += 1
            else:
                if same == 1:
                    new += before
                else:
                    new += str(same) + before
                
                before = temp
                same = 1
        
        if same == 1:
            new += temp
        else:
            new += str(same) + temp

        answer = min(answer, len(new))
    
    return answer

접근은 아래와 같다.

1. 문자열은 최대 len // 2 만큼 자를 수 있으므로, 1개씩 자르는 것부터 len//2개 자를 때 까지를 반복문으로 순회한다.
2. 이를 기준으로 문자열을 잘랐을 때, 반복이 되는 경우를 찾기 위해 이전 문자 값을 저장하는 before을 생성해 중복되는 문자열을 count해준다.
3. 중복되는 문자열이 있다면 count한 값을 앞에 붙여 새로운 문자열을 만든다.
4. 문자열 자르기를 탈출했을 때 마지막으로 잘린 문자열은 new에 붙지 않으므로 붙여준다.
5. answer에 더 작은 값을 업데이트 해준다.

문제 자체는 그렇게 어렵지 않았으나, 잘못 읽으면 나처럼 시간을 빼앗길 수 있으므로 신중하게 문제를 읽는 습관을 들이는 것이 좋을 것 같다.

문제 출처: 프로그래머스

문제 설명

🔎 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

시간을 고려해야 한다는 점을 제외하고는 그렇게 어려운 문제는 아니었다. 또 팰린드롬이라는 주제는 이미 다른 문제들에서도 많이 다뤘기 때문에 접근도 어렵지 않았다. 사실 문자열의 길이를 줄인다면 더 낮은 레벨을 부여 받지 않았을까 생각이 드는 문제였다.

문제를 푸는데 한 두번 밖에 시행착오를 겪지 않았지만, 다른 사람들의 풀이를 보니 내 풀이가 최적의 풀이는 아니었다.

<정답 코드>

def solution(s):
    answer = 1
    n = len(s)
    
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
            	mid = (i+j) // 2
                aft = s[j:mid:-1]
                if (i+j) % 2 == 0:
                    pre = s[i:mid]
                else: 
                    pre = s[i:mid+1]
                    
                if pre == aft:
                    answer = max(answer, j-i+1)
                        

    return answer

접근은 아래와 같다.

1. S를 구성하는 모든 문자를 점검하면서 현재 값과 같은 값을 가지는 위치를 모두 찾은 다음 비교한다.
2. 문자열을 비교할 때는 split된 문자열의 길이가 짝수일 때와 홀수일 때가 다르다.
   1. 홀수일 때는 중앙값을 제외한 나머지가 대칭을 이루면 팰린드롬이다.
   2. 짝수일 때는 중앙값이 없으므로 전체가 대칭을 이루면 팰린드롬이다.
3.  가장 큰 값을 answer로 업데이트한다. 가장 짧은 팰린드롬의 길이는 한 단어 (ex. 'a')이므로 최소값이 1이 출력될 수 있도록 수정해야한다.

시행착오 부분은 처음에 팰린드롬은 길이가 홀수여야한다는 착각과, 최소 길이가 1이라는 점을 망각했기에 틀린 답을 제출했었다. 이 부분만 제거하니 문제는 풀렸다.

다만 제출된  답안의 실행시간이 1647ms로 크게 나왔다는 점이 살짝 걸렸다.

다른 사람들의 풀이를 살펴보니 DP로 접근한 사람도 있고, early stop 조건을 삽입한 사람도 있었다. 다양한 풀이가 있는 만큼 내 코드도 개선될 부분이 있을거라 생각한다.

문제 출처: 프로그래머스

문제 설명

🔎 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

처음에는 최소공배수 문제인 줄 알았다. 하지만 심사관의 수가 변화할 수 있는데다가 심사 시간이 너무 크고, 무엇보다 기다렸다가 다른 사람한테 받는 경우가 더 빠른 경우도 있어서 아니라는 것을 알 수 있었다.

결국 이 문제는 이분탐색 문제였는데, 내가 이분탐색을 많이 연습하지 않아 접근하기 힘들어 결국 질문하기의 도움을 받아 풀 수 있었다.

<정답 코드>

def solution(n, times):
    answer = 0
    
    min_t = times[0]
    max_t = times[0] * n
    
    while True:
        mid = (min_t + max_t) // 2
        cnt = 0
        
        for i in times:
            cnt += mid//i
        
        if cnt < n:
            min_t = mid
        
        elif cnt >= n:
            max_t = mid
        
        if min_t == max_t - 1:
            answer = max_t
            break
        
    return answer

접근은 아래와 같다.

주어진 times 배열은 오름차순으로 정렬된 배열이라는 가정을 포함한다. (⬅ 문제 내에서 제시된 사항은 아니지만, 주어진 테스트 케이스는 위 가정을 모두 만족하였다.)

1. 입국심사가 가장 빠르게 끝날 때는 가장 빠른 심사관 한명에게 한명이 심사 받는 시간이므로 times[0], 가장 오래 걸린다하더라도 가장 빠른 심사관이 n명을 모두 점검하는 시간이므로 times[0] * n 을 각각 변수로 저장한다.
2. 이 두 변수를 가지고 이분탐색을 시작한다.
   1. mid 시간을 소요했을 때 심사 받은 사람의 수는 mid 시간에서 각 심사관의 소요 시간을 나눈 몫만큼이다.
   2. 통과한 사람의 수가 n보다 작다면 mid가 증가하는 방향으로 가야하므로 min_t를 mid로 업데이트 한다. 반대로 n보다 크다면 mid가 감소해야 하므로 max_t를 mid로 업데이트 한다.
   3. 결과적으로 정확히 n명을 통과하는 시간 중 최단 시간을 출력해야하므로 n == cnt라도 계속해서 시간을 줄여가면서 탐색한다.
   4. 최종 탐색 결과는 min_t와 max_t가 1만큼 차이날 때가 되므로 이 때의 시간을 출력한다.

이분탐색 문제는 원래 난이도가 높기도 하고 다른 문제들에 비해 문제 수도 많지 않아서 연습이 덜 되어 있었다. 이번 문제로 배열 안에서 필요한 시간을 도출하는게 아닌, 외부 조건을 도입하면서 이분 탐색을 하는 방법을 배울 수 있어서 좋았다.

문제 출처: 프로그래머스

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

처음 문제를 읽었을 때는 어떻게 접근 해야할지 고민을 오래한 문제다.

내 생각의 흐름은 이랬다.

순위를 정하는 문제 ➡ sort문제 ➡ 하지만 sort의 key를 설정하기 어려움 ➡ Tree 형식으로 질 때 마다 자식 노드로 추가해주면 되지 않을까? ➡ 이렇게 됐을 때 구현은 어떻게 해야하나..

이런 식으로 생각을 이어가면서 깨작깨작 작성하다보니 정답에 도달할 수 있었다.

<정답 코드>

def solution(n, results):
    answer = 0
    rank = {i + 1: [set(), set()] for i in range(n)}
    order = [0] * (n + 1)

    for win, lose in results:
        rank[win][0].add(lose)
        rank[lose][1].add(win)

    for _ in range(2):
        for i in rank.keys():
            for wins in rank[i][0]:
                rank[i][0] = rank[i][0].union(rank[wins][0])

            for loses in rank[i][1]:
                rank[i][1] = rank[i][1].union(rank[loses][1])

    for i in rank.keys():
        if len(rank[i][0]) + len(rank[i][1]) == n - 1:
            answer += 1

    return answer

접근은 아래와 같다.

어떤 선수의 총 경기 횟수가 n-1이면 해당 선수의 순위를 알 수 있다. (비기는 경우는 없기 때문에)

1. 선수 번호를 기준으로 해당 선수가 이긴 선수들과 패배한 선수들을 기록하는 dictionary를 만든다.
   1. 딕셔너리의 value는 두 set의 집합으로 만들어진다.
   2. 0번 index는 해당 선수가 이겼던 선수들을 기록했고, 1번 index에는 해당 선수가 졌던 선수들을 기록했다.
2. 경기 결과를 하나씩 살피면서 rank를 채워준다.
3. 채워진 rank를 순회하면서 한번 이겼던 선수에게 패배한 선수들이 있다면 채워주는 작업을 반복한다.
   1. 예를 들어 results가 [3, 1], [1, 2]이었다고 하면 최초의 rank는 {1: [(2), (3)], 2:[(1), ()], 3:[(), (1)]}이 된다. 이 때 아래 for문을 통해 한번 순회해주면 rank는 {1:[(2), (3)], 2:[(1), (3)], 3:[(),(1, 2)]가 되게 된다.
4. 마지막으로 모든 선수들 중 총 경기횟수가 n-1번 진행된 선수들만 count해준다.

운이 좋게 위 코드에서는 rank를 채워주는 작업이 총 3번 만에 모든 test case가 통과되었지만, 곰곰히 다시 생각해보니 rank에 업데이트가 새로 일어나지 않을 때 까지 반복해서 업데이트해주어야 진짜 정답이지 않을까 했다. (아닐수도 있음)

이렇게 보니 트리라기 보다 그래프 문제에 가까워 보였다. 실제 문제를 보니 그래프 문제로 분류되어 있었고 다른 사람들은 bfs나 플로이드-와샬 알고리즘으로 문제를 해결했다고 했다. 독특한 풀이를 했다고 좋아하긴 했지만, 남들이 생각하는 걸 생각하지 못했다는 점에서 약간의 아쉬움도 있었다.

이번 문제를 통해서 드디어 프로그래머스 level3에 도달할 수 있었다.

여러 번 시도하면서 운 좋게 몇일 전에 풀어봤던 문제가 나오기도 하고, level 3치고 쉬운 문제가 나온 적도 있었지만 항상 다른 문제에서 막혀서 뚫지 못했었는데 이번에는 둘다 모르는 문제였지만 천천히 생각하면서 푸니 통과할 수 있었다.

프로그래머스의 level이 현재 내 코딩 수준을 정의해주는 것은 아니지만 (현재까지 프로그래머스 문제만 300문제 가까이 풀었지만, 아직도 풀지 못한 level2, level3문제가 많다.) 꾸준히 성장하고 있고, 꼼수 부리지 않고 통과하겠다는 의지가 먹혀든 것 같아서 기분이 좋았다.

문제 출처: 백준 온라인 저지

문제 설명

🔎 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

<정답 코드>

from heapq import heapify, heappop
from itertools import combinations

while True:
    inp = list(map(int, input().split()))
    if inp == [0]:
        break

    n = inp[0]
    inp = inp[1:]
    com = list(combinations(inp, 6))
    heapify(com)

    while com:
        print(*heappop(com))

    print()

combinations를 통해 구현하는 간단한 문제였다.

접근은 아래와 같다.

1. 입력 받은 배열을 k와 S로 구분한 후, combinations를 이용해 6개를 뽑는 집합을 만든다.
2. 집합을 heapq를 통해 정렬한 후 heappop하면서 오름차순으로 뽑는다.

이 전에 비슷한 문제들을 풀었던 것과 달리 min heap을 활용해서 정렬해보았다.

문제 출처: 백준 온라인 저지

문제 설명

🔎 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다.

단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다.

- 비용은 대칭적이지 않다. 
- 즉, W[i][j] 는 W[j][i]와 다를 수 있다.
- 모든 도시간의 비용은 양의 정수이다.
- W[i][i]는 항상 0이다.
- 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

위 예제를 그림으로 나타내면 이와 같다.

여기서 정답인 경로는 여러가지가 존재하지만, 하나만 꼽아보자면 2 ➡ 0 ➡ 1 ➡ 3 ➡ 2 순으로 순회할 경우 총 비용이 35로 최소가 된다.

이런 방식으로 접근을 한다면 그래프를 순회하는 알고리즘 중 하나를 사용해야 한다는 것을 알 수 있다.

나는 여기서 DFS를 이용하기로 했다.

<정답 코드>

def dfs(x, val, depth=1):
    global cost
    global first
    global n

    if depth == n:
        for nx, _cost in graph[x]:
            if nx == first:
                cost = min(cost, val+_cost)
        return

    if visit[x]:
        return

    visit[x] = True

    for nx, _cost in graph[x]:
        if not visit[nx]:
            dfs(nx, val+_cost, depth+1)
            visit[nx] = False


n = int(input())
graph = [[] for _ in range(n)]
cost = float('inf')

for i in range(n):
    arr = list(map(int, input().split()))
    for j in range(n):
        if i == j or arr[j] == 0: continue
        graph[i].append((j, arr[j]))

for i in range(n):
    visit = [False] * n
    first = i
    dfs(i, 0)

print(cost)

우선은 2차원 배열형태로 접근하는게 아니라 그래프 형태로 접근하기 위해서 입력을 그래프 형식으로 전환한 뒤 시작하였다.

접근은 아래와 같다.

1. 모든 도시에서 한번씩 시작하며 dfs를 순회한다.
2. dfs를 순회할 때는 시작 지점인 first를 기록하고 시작한다.
3. 한번 방문하고 함수를 빠져나오게 될 때 visit을 초기화 해주어 모든 경로를 탐색할 수 있게 한다.
4. dfs의 depth가 n이 될 때 까지 recursion하며, depth가 n일 때 현재 도시에서 first로 갈 수 있으면 cost를 업데이트 해준다.

처음에는 DP나 다익스트라 문제인 줄 알았다.

하지만, 모든 도시를 다 방문해야하고 출발 지점이 정해져있지 않았으며 한번 방문한 도시는 다시 방문할 수 없었기에 dfs를 통해 접근해야 한다는 사실을 깨달았다.