greentea31's Note

https://leetcode.com/problems/network-delay-time/

풀이 과정

노드와 간선이 주어질 때, 노드 k에서 시작해서 모든 노드를 순회하는데 걸리는 최소 시간을 구하는 문제이다. 순회가 불가능하면 -1을 출력해야 한다.

그래프에서 최소 거리, 최소 시간 문제를 풀 때는 BFS, 다익스트라, 플로이드, 벨만포드 알고리즘을 떠올릴 필요가 있고 이 문제에서는 간선의 가중치가 음수가 아님이 보장되므로 다익스트라를 통해서 문제를 해결하면 된다.

시작점 K와 나머지 모든 점의 최소 거리를 구하고, 거리의 최대값이 모든 점을 방문하는데 걸리는 시간이므로 이를 출력해주면 된다.

모든 정점으로의 거리가 추가되었는지 확인하고, 추가되지 않은 정점이 있으면 모든 정점을 순회하는게 불가능하다는 의미이므로 -1을 리턴해주면 된다.

소스 코드

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        dist = collections.defaultdict(int)
        for u, v, w in times:
            graph[u].append((v, w))
        Q = [(0, k)]
        
        while Q:
            time, node = heapq.heappop(Q)
            if node not in dist:
                dist[node] = time
                for v, w in graph[node]:
                    temp = time + w
                    heapq.heappush(Q, (temp, v))
        
        if len(dist) == n:
            return max(dist.values())
        return -1

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 987654321;
int d[20005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int V, E, u, v, w;
    cin >> V >> E;

    for (int i = 1; i < V+1; i++) { // 전체 정점 거리 무한대 초기화
        d[i] = INF;
    }

    int start;
    cin >> start;

    vector<pair<int, int>> adj[20005];

    for (int i = 0; i < E; i++) { // 인접 리스트
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 최소 힙
    // (정점까지의 거리, 정점 번호)를 저장하는 최소 힙을 선언한다.
    d[start] = 0; // 시작 정점까지의 거리는 0이다.
    pq.push(make_pair(d[start], start)); // 시작 거리 0 최소화후 최소힙 삽입


    while(!pq.empty()) {
        pair<int, int> cur = pq.top(); pq.pop();
        if (d[cur.second] != cur.first) continue;
        for (int i = 0; i < adj[cur.second].size(); i++) {
            pair<int, int> next = adj[cur.second][i];
            if (d[next.second] <= d[cur.second] + next.first) continue;
            d[next.second] = d[cur.second] + next.first;
            pq.push(make_pair(d[next.second], next.second));
        }
    }

    for (int i = 1; i < V+1; i++) {
        if (d[i] == INF) cout << "INF\n";
        else cout << d[i] << '\n';
    }

    return 0;
}

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

이 문제의 정답이기도 하다.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        Q = [(0, k)]  # 시작점과 시작 거리
        dist = collections.defaultdict(int)
        
        while Q:
            time, node = heapq.heappop(Q)
            if node not in dist:  # 거리 저장이 안되어있으면
                dist[node] = time  # 거리 저장
                for v, w in graph[node]:
                    temp = time + w
                    heapq.heappush(Q, (temp, v))
        
        if len(dist) == n:
            return max(dist.values())
        return -1

https://leetcode.com/problems/network-delay-time/

이 문제의 정답이기도 하다.

출처

https://blog.encrypted.gg/941?category=773649 

https://search.shopping.naver.com/book/catalog/32456486633?cat_id=50010920&frm=PBOKMOD&query=%ED%8C%8C%EC%9D%B4%EC%8D%AC+%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+%EC%9D%B8%ED%84%B0%EB%B7%B0&NaPm=ct%3Dl78vgtt4%7Cci%3Df701ad06257574c041af4ed5be5c108b6047f8ac%7Ctr%3Dboknx%7Csn%3D95694%7Chk%3Da3fb28618a3308e23e626cf38260466b81380bd4 

https://leetcode.com/problems/course-schedule/

풀이 과정

어떤 지점을 방문하기 위해 방문해야 하는 선행 방문 지점이 주어질 때, 주어진 코스가 순회 가능한지 여부를 구하는 문제이다.

예를 들어 1을 방문하기 위해서 0을 방문해야 하고, 0을 방문하기 위해서 1을 방문해야 한다면, 두 지점 모두 방문이 불가능하므로 코스가 순회가 불가능하다고 할 수 있다.

문제에서 주어진 prerequisites를 그래프의 간선으로 생각해 그래프로 모델링 한 후, 그래프에서 사이클이 존재하면 코스가 순회 불가능, 사이클이 존재하지 않으면 코스가 순회가 가능하다고 판단해주면 된다.

visit set으로 방문점 파악, route set으로 사이클 존재 여부를 파악하게 하여 코드를 작성하였다. 방문점, 사이클 존재 파악시 in을 사용하면 시간복잡도가 O(N)이라 비효율적인 코드가 아닌가 하는 생각이 들 수 있다.

Python의 경우 list, tuple 자료형에서는 in 사용시 하나하나 순회하기 때문에 O(N)이지만, set이나 dictionary에서는 내부적으로 hash를 통해서 자료들을 저장하기 때문에 해시 충돌이 정말 많이 발생하지 않는 이상 O(1)로 작동한다.

소스 코드

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        route = set()
        visit = set()
        graph = collections.defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)
        
        def dfs(x):
            if x in route:
                return False
            if x in visit:
                return True
            
            visit.add(x)
            route.add(x)
            
            for arrive in graph[x]:
                if not dfs(arrive):
                    return False
            
            route.remove(x)
            return True
    
        for x in list(graph):
            if not dfs(x):
                return False

        return True

https://leetcode.com/problems/reconstruct-itinerary

풀이 과정

JFK에서 시작하는, 주어진 모든 비행 티켓을 사용하는 여행 경로를 구하는 문제이다. 경로는 여러가지가 존재할 수 있지만 사전식 순서로 앞선 경로만을 출력해야 한다.

비행기 티켓을 딕셔너리에 전부 넣어놓고, JFK에서 시작해 DFS 방식으로 사전식 순서가 앞선 도착지를 우선으로 탐방하여 문제를 해결하였다.

소스 코드

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        answer = []
        for depart, arrive in sorted(tickets, reverse=True):
            graph[depart].append(arrive)
        
        def dfs(x):
            while graph[x]:
                dfs(graph[x].pop())
            answer.append(x)
        
        dfs('JFK')
        return answer[::-1]

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

풀이 과정

친분 관계 사이를 기반으로 튜터-튜티 지정이 가능하며, 교육 자료는 튜터 -> 튜티 방향으로 전달할 수 있다. 교육생간의 친분 관계가 포레스트인 그래프로 주어질 때 모든 교육생에게 자료가 전달되기 위해 찬솔이가 전해줘야 하는 인원수의 최소가 될 때의 튜터-튜티 관계를 정하는 경우의 수를 구하는 문제이다.

각 연결요소에 속해있는 정점의 개수를 정답 변수에 곱하는 방법으로 답을 구할 수 있다. 1 - 2 - 3, 4 - 5 - 6 - 7 - 8 이렇게 연결되어 있을 때의 경우는 3x5 = 15개의 경우의 수가 나올 것이다.

소스 코드

import sys
import collections


def bfs(x, visit, graph):
    q = collections.deque([x])
    visit[x] = True
    number = 1

    while q:
        cur = q.popleft()
        for nxt in graph[cur]:
            if visit[nxt]:
                continue
            q.append(nxt)
            visit[nxt] = True
            number += 1

    return number


graph = collections.defaultdict(list)
N, M = map(int, sys.stdin.readline().split())
visit = [False for _ in range(N+1)]
answer = 1
mod = 1000000007

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

for v in range(1, N+1):
    if not visit[v]:
        answer *= bfs(v, visit, graph)
        answer %= mod

print(answer)

https://school.programmers.co.kr/learn/courses/30/lessons/42579

풀이 과정

각 노래의 장르와, 플레이 된 횟수가 주어질 때, 가장 많이 플레이된 장르의 노래가 먼저 나오게끔, 각 장르별로 많이 재생된 2개의 노래씩을 모아 베스트 앨범을 만드는 문제이다.

장르: [장르 재생 횟수, [[노래 인덱스, 재생 횟수], [노래 인덱스, 재생 횟수]...] 꼴의 딕셔너리를 만들고, 장르 재생 횟수와 노래 재생 횟수로 적절히 정렬을 수행하여 문제를 해결하였다.

코드에서 딕셔너리 genres_dict와 딕셔너리를 정렬된 리스트로 표현한 temp를 중간에 출력한 테스트 결과이다.

소스 코드

import collections

def solution(genres, plays):
    genres_dict = collections.defaultdict(list)
    for index, genre in enumerate(genres):
        if not genres_dict[genre]:
            genres_dict[genre].append(plays[index])
            genres_dict[genre].append([[index, plays[index]]])
        else:
            genres_dict[genre][1].append([index, plays[index]])
            genres_dict[genre][0] += plays[index]
    temp = sorted(genres_dict.values(), key=lambda x: x[0], reverse=True)
    for song in temp:
        song[1].sort(key=lambda x: x[1], reverse=True)
    answer = []
    for song in temp:
        if len(song[1]) >= 2:
            answer.append(song[1][0][0])
            answer.append(song[1][1][0])
        else:
            answer.append(song[1][0][0])
        
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/1829

풀이 과정

배열로 주어진 그림에서 몇 개의 영역이 있는지, 가장 넓은 영역의 크기는 얼마인지 구하는 문제이다.

그래프에서 연결 요소의 개수와 가장 큰 연결 요소의 크기를 구해달라는 말과 같고, 색칠이 되어 있고, 아직 방문하지 않은 모든 좌표에 대해 BFS 혹은 DFS를 진행해주면 된다.

소스 코드

#include <vector>
#include <queue>
using namespace std;

bool visit[101][101];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

int bfs(int y, int x, vector<vector<int>>& picture, int m, int n) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));
    int max_size = 1;
    int color = picture[y][x];
    
    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (0 <= ny && ny < m && 0 <= nx && nx < n && !visit[ny][nx] && color == picture[ny][nx]) {
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
                max_size++;
            }
        }
    }
    
    return max_size;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visit[i][j] && picture[i][j] != 0) {
                int temp = bfs(i, j, picture, m, n);
                number_of_area++;
                if (max_size_of_one_area < temp) max_size_of_one_area = temp;
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            visit[i][j] = false;
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

https://leetcode.com/problems/subsets/

풀이 과정

주어진 배열의 부분 집합을 구하는 문제이다.

재귀로 배열의 각 인덱스에 해당하는 원소가 부분 집합에 들어갈지, 안들어갈지 판단해주면서 answer 배열에 추가해주었다. 어떤 배열이 주어지던, 부분 집합에 공집합은 반드시 포함되므로, 정답 배열에 공집합을 넣어놓고 재귀 함수를 수행하였다.

소스 코드

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        answer = [[]]
        output = []
        
        def subset(index):
            if index >= len(nums):
                return
            output.append(nums[index])
            answer.append(output[:])
            subset(index+1)
            output.pop()
            subset(index+1)
        
        subset(0)
        return answer

https://leetcode.com/problems/combination-sum/

풀이 과정

배열로 주어진 수들의 중복조합의 합이 target이 되는 경우를 구하는 문제이다.

https://greentea31.tistory.com/196?category=947572 

위 문제를 해결했던 것 처럼 어떤 수를 고르고, 안고르고의 경우를 재귀함수로 계산하게끔 하였다. 단 이번 문제는 중복조합이므로, 어떤 수를 골랐어도 다음에도 또 고를 수 있으므로, 어떤 수를 골라서 sum_value가 증가하는 경우, 고를지 말지 판별해야 하는 index가 증가하게끔 하지 않았다.

어떤 수를 고르지 않는 경우에는 index+1을 시켜줘야 한다.

i 안 고름 -> i 안 고름 -> i 안 고름 -> 무한반복 -> i 고름

i 고름

는 같은 경우인데 연산 과정만 늘어나고 재귀를 탈출하지도 못하기 때문이다.

소스 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        output = []
        
        def combination(index, sum_value):
            if sum_value >= target:
                if sum_value == target:
                    answer.append(output[:])
                return
            if index >= len(candidates):
                return
                
            output.append(candidates[index])
            combination(index, sum_value + candidates[index])
            output.pop()
            combination(index+1, sum_value)
        
        combination(0, 0)
        return answer

https://leetcode.com/problems/combinations/

풀이 과정

주어진 n개의 원소의 리스트에서 k개의 숫자로 이루어진 조합을 구하는 문제이다.

https://greentea31.tistory.com/111?category=939228 

위의 글의 코드를 구현하였다. 1~4까지의 수를 원소로 가진 리스트에서 2개를 뽑아 조합을 만들어야 한다면 1을 고르는 것과 안고르는 것, 2를 고르는 것과 안고르는 것, 3을 고르는 것과 안고르는 것, 4를 고르는 것과 안고르는 것... 이런식으로 구하다 골라야 하는 수가 4를 넘어가거나, 이미 고른 수가 2를 넘어가면 그만두게 하고, 이미 고른 수가 2개가 되는 경우마다 정답 배열에 추가해 주면 모든 조합을 구할 수 있다.

책에서 본 좋은 코드도 재귀 2에 기록해 두었고, itertools 모듈의 combinations 함수를 사용하면 문제를 더 쉽게 해결할 수 있다.

소스 코드

재귀 1

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        answer = []
        output = [-1 for _ in range(k)]
        
        def combination(index, selected):
            if selected == k:
                answer.append(output[:])
                return
            if index > n:
                return
            
            output[selected] = index
            combination(index+1, selected+1)
            combination(index+1, selected)
        
        combination(1, 0)
        return answer

재귀 2

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []
        
        def combination(elements, start, k):  # 추가된 원소, 탐색 시작점, 넣어야 될 남은 원소 개수
            if k == 0:  # 다 넣었으면 정답 추가
                results.append(elements[:])
                return
            
            for i in range(start, n+1):
                elements.append(i)  # i를 넣는 경우
                combination(elements, i+1, k-1)
                elements.pop()  # i를 넣지 않는 경우
        
        combination([], 1, k)
        return results

itertools

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(itertools.combinations(range(1, n+1), k))