[TIL][Krafton Jungle] 2주차 - (3) : DFS 알고리즘 공부

오늘은 BFS 문제 풀이를 팀원과 서로 공유하고 DFS 문제 풀이를 시작했다.

 

---

BaekJun - # 21606 : 아침산책 (DFS)

완전히 하나로 연결된 N개의 노드의 서로 다른 경로의 수를 세는 문제인데,

노드가 실내거나 실외이다.

경로는 반드시 실내에서 시작해서 서로 다른 실내로 끝나며

1 -> 3 과 3 -> 1은 다른 경로로 보는 것이다.

 

이 문제의 특이한 점은 서브 테스크로 문제 배점을 나눈다는 점이었다.

 

주목할 점은 N의 최대 제한이 10의 5승이라는 점.

(대충 NlogN 보다 높은 시간 복잡도를 가진다면 앙 시간초과 띠~ 라는 뜻)

 

나는 2번과 5번 테스크에서 시간 초과가 발생했다.

 

시간 초과가 발생한 로직은 다음과 같다.

코드를 보기 전 말로 설명한다면,

 

1. 실내인 노드를 하나씩 DFS에 넣는다.

2. DFS에서 해당 노드의 연결 노드가 실내라면 경로를 +1 한다.

3. DFS에서 해당 노드의 연결 노드가 실외라면 DFS를 재귀한다.

 

하지만 이 방법은 O(n^2) 이므로 시간 초과가 발생한 것.

더 시간을 줄이기 위해 다른 방법을 생각 해내야 했다.

 

그래서 생각한 방법은 실외만 순회하며 실외와 붙어 있는 실내의 노드의 수를 세는 것.

그럼 확통때 배운 경우의 수로

실외에 붙어있는 실내의 노드의 수 (k) x k-1 

를 통해 구할 수 있다.

 

하지만 실내끼리 붙어있는 경우의 수도 고려해야 하므로

 

실외를 for문 돌린 후 실내끼리 붙은 경우 경로 +1을 해준다.

 

코드는 다음과 같다.

from collections import deque
import sys
import heapq
sys.setrecursionlimit(10**6)

n = int(sys.stdin.readline())
tree = {}

isInside = list(map(int,sys.stdin.readline().strip()))
visited = [False for _ in range(n+1)]
count = 0
while True:
    try:
        u , v = map(int,sys.stdin.readline().strip().split())
        if not u in tree:
            tree[u] = [v]
        else:
            tree[u].append(v)
        if not v in tree:
            tree[v] = [u]
        else:
            tree[v].append(u)
    except:
        break



def dfs(v):
    inside_count = 0
    visited[v] = True
    for i in tree[v]:
        if not visited[i]:
            if isInside[i-1]:
                inside_count += 1
                continue
            else :
                inside_count += dfs(i)
    return inside_count

for i in tree.keys():
    if not isInside[i-1]:
        if not visited[i]:
            inside_count = dfs(i)
            count += inside_count*(inside_count-1)
    else:
        for j in tree[i]:
            if isInside[j-1]:
                count +=1  


print(count)

---

 

BaekJun - #1916 : 최소 비용 구하기(다익스트라)

---

문제는 n개의 정점을 잇는 m개의 버스 노선이 서로 다른 비용을 가지는데

특정 start 부터 end 까지 갈 때 최소로 드는 버스 비용을 구하는 문제였다.

 

이는 다익스트라를 활용하는 전형적인 최소 가중치 그래프 탐색이라고 생각했다.

 

하지만 문제는 '메모리 초과'라는 의외의 구석에서 발생했다.

 

처음 제출했던 코드는 다음과 같다.

from collections import deque
import sys
import heapq
sys.setrecursionlimit(10**6)

# test = [1,2]
# a,b = test
# print(a)
# print(b)
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
city = {}
visited = [False for _ in range(n+1)]

for _ in range(m):
    v1,v2,cost = map(int,sys.stdin.readline().strip().split())
    if not v1 in city:
        city[v1] = [[cost,v2]]
    else :
        city[v1].append([cost,v2])

start , end = map(int,sys.stdin.readline().strip().split())

def dijkstra(start):
    global end
    heap = []
    heapq.heapify(heap)
    heapq.heappush(heap,[0,start])
    while True:
        cost,vertex = heapq.heappop(heap)
        if vertex == end:
            return cost
        if vertex in city:
            for i,j in city[vertex]:
                if not visited[j]:
                    heapq.heappush(heap,[cost+i,j])
        visited[vertex] = True

print(dijkstra(start))

우선순위 큐인 힙 자료구조를 통해 최소의 경로 탐색을 수행했다.

모든 우회하는 경로를 전부 힙에 넣지만 결국 최소의 값만이 바로바로 실행되기에 메모리양은 신경쓰지 않는 알고리즘이다.

 

그래서 결국엔 메모리가 초과됬다.

그래서 메모리를 줄이기 위해선

이전 경로보다 우회한 경로들은 전부 heap에 넣지 않도록 하는 알고리즘이 추가 되어야 했다.

 

def dijkstra(start):
    global end
    costMin = [float('inf')]*(n+1)
    heap = []
    heapq.heapify(heap)
    heapq.heappush(heap,[0,start])
    costMin[start] = 0
    while heap:
        cost , vertex = heapq.heappop(heap)
        visited[vertex] = True
        if vertex == end:
            return cost
        if vertex in city:
            for i,j in city[vertex]:
                if not visited[j] and costMin[j] > cost + i:
                    heapq.heappush(heap,[cost+i,j])
                    costMin[j] = cost+i

그래서 추가해 넣은 것이 costMin 리스트이다.

해당 리스트의 인덱스로 매칭되는 정점에 도착하는 최소의 비용을 저장하는 리스트이다.

 

주의해야 할 점은 마지막 if문인 costMin[j] > cost + i 이었다.

 

처음엔 not costMin[j] < cost + i 로 조건문을 걸었더니 메모리초과가 해결되지 않았는데,

이는 같은 비용이 드는 여러가지의 경우가 전부 heap에 들어가기 때문에 발생한 것이었다.

우리가 원하는 건 경우의 수가 아닌 최소의 비용이 몇인지이기 때문에 더 적어지는 경우만 갱신해주면 되었다.

 

 

 

깨알 상식 백준 문제풀이용 python 문법

---

1. 다들 알고 있었는데 나만 몰랐을 지도 모르는 깨알 리스트 값 저장 꿀팁

 

test = [1,2]

a,b = test

print(a)

print(b)

리스트의 인덱스를 한번에 저장하고 싶을 때 나눠서 저장이 가능하다는 점..!

1

2

출력됩니다.