👩‍🎓공부 - 2024.02.21 코딩 문제풀이

프로그래머스 - 가장 먼 노드

DFS로 풀다가 한참 해맸습니다... 심지어 예전에 유사문제 한번 풀어봤던 것 같은데...
어쨋든 이 문제의 쟁점은 BFS로 level(depth)를 구할 수 있는가 없는가 입니다.

그림과 같이 노드의 간선이 2개 이상인 경우에는 DFS로 노드의 level을 구하기 매우매우매우 어렵기때문에 BFS로 레벨을 구하는 형식으로 접근해야 합니다.

from collections import deque
import sys

시간초과 방지용으로 sysinput 받아서

def solution(n, edge):
    input = sys.stdin.readline
    

solution 함수 내에 넣어줍시다.

    def bfs(n):
        level = 1
        que.append(n)
        visited[n] = 1

먼저 BFS 함수를 작성할껍니다. 초기 레벨 0은 따로 지정해줄꺼고 레벨 1부터 시작합시다.
지금 막 들어온 노드 1은 방문처리 해주고 que에 넣어줍시다.

        while que:
            for i in range(len(que)):
                a = que.popleft()

BFS level처리의 핵심입니다. BFS를 딱 que값만큼만 돌리면 해당 level값만큼만 노드를 탐색한 샘이 되기 때문에 BFS에서 level을 구할 수 있습니다. 자세한 건 제 예전 포스팅 첨부하겠습니다.
https://velog.io/@ghost_dog/%EA%B3%B5%EB%B6%80-2024.01.19-%EC%98%A4%EB%8A%98%EC%9D%98-%EB%B0%B1%EC%A4%80-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4

                for i in range(len(graph[a])):
                    if not visited[graph[a][i]]:
                        visited[graph[a][i]] = 1
                        que.append(graph[a][i])

현재 탐색중인 노드를 인덱스 차원으로 접근하여 graph[노드] = 연결된노드 형식으로 짤껍니다.
만약 탐색중인 노드와 연결된 노드 중 아직 탐색을 안한 노드가 있다면 방문처리를 해주고 que에 추가하여 탐색 예비후보로 지정합시다.

                        ans[graph[a][i]] = level
                        print(graph[a][i],level)
            level += 1

ans라는 리스트에 해당 노드에 접근하면 level을 표시하도록 코딩해줍시다.
그리고 que에 해당하는 걸 다 돌았으면 (현재 level이 끝났으면) level을 1 올려주도록 합시다.

    graph = [[] for _ in range(n+1)]
    while edge:
        [x,y] = edge.pop() 
        graph[x].append(y)
        graph[y].append(x)

시간초과를 피하는 부분입니다.
원래 저는 그래프를 짤 때 습관적으로

    graph = [[0]*(n+1) for _ in range(n+1)]
    while edge:
        [x,y] = edge.pop() 
        graph[x][y] = graph[y][x] = 1

로 작성했었는데 이러면 정상적으로 작동은 하나 DFS는 물론이고 BFS에서까지도 [0]이 쓸데없는 공간을 잡아먹어 시간초과가 뜨곤 했습니다. 따라서 [0]으로 선언하기보단 아예 빈 리스트에 인덱스만 집어넣을 수 있도록 만들어주고 해당 인덱스에 접근하면 value 값으로 그와 연결된 노드만 표시하게끔 코딩했씁니다.

    visited = [0]*(n+1)
    que = deque([])
    ans = [0]*(n+1)
    ans[1] = 0
    bfs(1)

방문배열 초기화, que선언, ans 선언 등을 해주고 맨 첫 노드인 1은 level 0으로 설정해줍시다. 그리고 1을 시작으로 bfs를 돌리면 됩니다.

    return ans.count(max(ans))

마지막으로 level이 가장 큰 노드의 갯수를 구하라 했으므로 max(ans)로 가장 큰 레벨을 구해 ans에 얼만큼 있는지 count해줍시다.

---

---

프로그래머스 - 스킬트리

소마 1,2번에 구현 문제가 나온다길래 구현 문제 연습겸 풀어봤습니다.

스킬과 스킬트리라는 변수가 주어집니다. 이 스킬이라는 리스트에 A,B,C가 있으면 스킬트리라는 원소값 순서는 무조건 A가 먼저, 그다음 B, 그다음 C가 와야합니다. 뭐가 중간에 껴있어도 크게 상관없습니다.

이 문제의 핵심은 스킬 리스트에 빠진 원소가 존재하는 경우입니다. 예를 들어 A->K(아무거나)->C라면 A다음에 와야 할 B가 빠져있으므로 스킬트리가 될 수 없습니다.

    ans = 0
    skill = list(skill)

일단 ans를 0으로 선언하고 skill을 list로써 활용하기 쉽게 분리해주겠습니다.

    for i in range(len(skill_trees)):
        tmp = -1
        boolean = False

이제 스킬 트리를 탐색하여 스킬 리스트와 대조해줄 겁니다. tmp값은 기재하겠지만 해당 스킬 트리 어느 인덱스에 스킬이 위치하는가를 기재해줄 겁니다. 값을 작으면~ 이라는 조건으로 대조할거라 -1로 초기화하였습니다.

        for k in range(len(skill)):
            if boolean == True:
                break

스킬 리스트와 대조를 시작하겠습니다. boolean값이 true면 스킬 리스트 순서에 맞지 않다고 가정하여 루프를 깨겠습니다.

            elif skill[k] not in skill_trees[i]:
                tmp = 100
                continue

스킬 리스트가 A->B->C 라고 가정하고 스킬트리가 A->K->C라고 가정해봅시다. A조사는 무난히 넘어갔는데 스킬트리에 B라는 스킬 리스트가 없는 걸 확인할 수 있습니다. 이렇게 되버리면 B이후의 어떤 스킬 리스트도 스킬트리에 존재해서는 안되므로 tmp에 100이라는 고값을 대입해 무슨 값이든 튕겨버리도록 합시다.

            elif skill_trees[i].index(skill[k]) < tmp:
                boolean = True
                continue

만약 현재 조사중인 스킬 트리 내부의 스킬 리스트 위치가 이전에 조사한 스킬 트리 내부의 스킬 리스트 위치보다 작다면 스킬 리스트 순서에 맞지 않으므로 boolean = True를 유도해서 최종 답을 올리지 못하도록 합시다.

            tmp = skill_trees[i].index(skill[k])

다음 스킬 리스트와 비교하기 위해서 tmp를 저장해줍시다.

        if boolean == False:
            ans += 1
    return (ans)

위 과정을 걸쳤음에도 불구하고 boolean값이 False가 나왔다면 최종 답 + 1을 해주고 return 해줍시다.

---

---