낭중지추

1. 문제

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

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

하나의 네트워크에 n개의 노드가 있고, 간선 정보 times가 주어진다.

times[i] = (u, v, w)

• u → v 로 가는 데 걸리는 시간은 w
• 시작 노드 k에서 신호를 보냈을 때
• 모든 노드가 신호를 받는 최소 시간을 구하는 문제
• 도달 불가능한 노드가 있다면 -1 반환

2. 풀이

이 문제는 다음 조건을 만족한다:

• 방향 그래프
• 가중치 존재
• 단일 시작점
• 최단 거리 문제

따라서 다익스트라(Dijkstra) 알고리즘을 사용하면 된다.

우리가 구해야 하는 것은 시작점 k에서 각 노드까지의 최단 거리 그 중 가장 큰 값

코드 설계:

1. 그래프 생성
2. 다익스트라 수행
3. 모든 노드 방문 여부 확인
4. 최단 거리 중 최대값 반환

구현 코드:

import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times, n, k):

        # 1. 그래프 생성
        graph = defaultdict(list)
        for time in times:
            graph[time[0]].append((time[2], time[1]))
        
        # 2. 다익스트라 알고리즘
        costs = {}
        pq = []
        heapq.heappush(pq, (0, k))

        while pq: 
            cur_cost, cur_node = heapq.heappop(pq)

            # 이미 방문한 노드는 건너뜀
            if cur_node not in costs:
                costs[cur_node] = cur_cost

                for next_cost, next_node in graph[cur_node]:
                    next_cost = cur_cost + next_cost
                    heapq.heappush(pq, (next_cost, next_node))

        # 3. 방문 못한 노드 확인
        if len(costs) != n:
            return -1

        # 4. 최소값 중 최대값 리턴
        return max(costs.values())

1. 문제

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

• 1 <= m, n <= 100

m × n 격자(grid)가 있다.

로봇은 왼쪽 위 (0,0) 에서 시작해서

오른쪽 아래 (m-1, n-1) 까지 이동해야 한다.

단,

• 오른쪽 →
• 아래 ↓

이동 가능하다.

목적지까지 갈 수 있는 서로 다른 경로의 개수를 구하라.

2. 풀이

이 문제를 처음 보면 자연스럽게 이렇게 생각하게 된다.

현재 위치에서

• 위에서 왔거나
• 왼쪽에서 왔거나

즉 어떤 칸 (r, c)에 도착하는 경우의 수는(r-1, c)에서 오는 경우 + (r, c-1)에서 오는 경우

이걸 그대로 재귀로 표현하면 DFS가 된다.

dfs(r, c)

= dfs(r-1, c) + dfs(r, c-1)

시작점은 경로가 1. 

dfs(0,0) = 1

순수dfs로 풀면 시간초과가 나기때문에 메모이제이션으로 풀어야한다.

먼저, 이중리스트로 구현해보았다.

memo 배열 설계

memo = [[-1] * n for _ in range(m)]

memo[r][c] =
    -1 → 아직 계산 안됨
    값 → 해당 위치까지 오는 경로 수

# 이중리스트 구현

class Solution:
    def uniquePaths(self, m, n):

        # 메모 테이블 생성
        memo = [[-1] * n for _ in range(m)]

        def dfs(r, c):

            unique_paths = 0

            # base case (출발점)
            if r == 0 and c == 0:
                memo[r][c] = 1

            # 아직 계산 안된 경우만 계산
            if memo[r][c] == -1:

                # 위에서 내려오는 경우
                if r - 1 >= 0:
                    unique_paths += dfs(r - 1, c)

                # 왼쪽에서 오는 경우
                if c - 1 >= 0:
                    unique_paths += dfs(r, c - 1)

                memo[r][c] = unique_paths

            return memo[r][c]

        return dfs(m - 1, n - 1)

# 해시맵(딕셔너리) 구현

class Solution:
    def uniquePaths(self, m, n):

        memo = {}

        def dfs(r, c):

            # base case
            if r == 0 and c == 0:
                return 1

            # 이미 계산됨
            if (r, c) in memo:
                return memo[(r, c)]

            paths = 0

            if r > 0:
                paths += dfs(r - 1, c)

            if c > 0:
                paths += dfs(r, c - 1)

            memo[(r, c)] = paths
            return paths

        return dfs(m - 1, n - 1)

Bottom - up 방식으로도 구현해볼 수 있다.

아래, 오른쪽으로밖에 이동 못하기 때문에 가생이? 것들의 paths는 1일것으로 이것을 베이스케이스로 사용.

#이중리스트

class Solution:
    def uniquePaths(self, m, n):

        # DP 테이블 생성
        dp = [[0] * n for _ in range(m)]

        # 첫 행 = 1 (오른쪽만 이동 가능)
        for c in range(n):
            dp[0][c] = 1

        # 첫 열 = 1 (아래만 이동 가능)
        for r in range(m):
            dp[r][0] = 1

        # 점화식 채우기
        for r in range(1, m):
            for c in range(1, n):
                dp[r][c] = dp[r-1][c] + dp[r][c-1]

        return dp[m-1][n-1]

#해시맵(딕셔너리)

class Solution:
    def uniquePaths(self, m, n):

        dp = {}

        # 첫 행
        for c in range(n):
            dp[(0, c)] = 1

        # 첫 열
        for r in range(m):
            dp[(r, 0)] = 1

        # 점화식
        for r in range(1, m):
            for c in range(1, n):
                dp[(r, c)] = dp[(r-1, c)] + dp[(r, c-1)]

        return dp[(m-1, n-1)]

1. 문제

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]

Output: 15

Explanation: You will start at index 1.

- Pay 15 and climb two steps to reach the top.

The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

Explanation: You will start at index 0.

- Pay 1 and climb two steps to reach index 2.

- Pay 1 and climb two steps to reach index 4.

- Pay 1 and climb two steps to reach index 6.

- Pay 1 and climb one step to reach index 7.

- Pay 1 and climb two steps to reach index 9.

- Pay 1 and climb one step to reach the top.

The total cost is 6.

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

2. 풀이

1) DFS(순수 재귀)

dfs(i) = i번째 위치(0..n)에 도달하는 최소 비용

top은 n이므로 최종 답은 dfs(n).

점화식:

• i에 도달하려면
  • i-1에서 한 칸 올라오거나(그때 cost[i-1] 지불)
  • i-2에서 두 칸 올라온다(그때 cost[i-2] 지불)

class Solution:
    def minCostClimbingStairs(self, cost):
        n = len(cost)

        def dfs(i):
            if i <= 1:     # 시작점(0 또는 1) → 비용 0
                return 0

            return min(
                dfs(i - 1) + cost[i - 1],
                dfs(i - 2) + cost[i - 2]
            )

        return dfs(n)

• 시간복잡도: O(2^n) (중복 호출 많음)
• 공간복잡도: O(n) (재귀 스택)

2) DP Top-down (Memoization)으로 개선하기

핵심

순수 재귀는 dfs(i)를 여러 번 다시 계산한다.

그래서 dfs(i) 값을 한 번만 계산해서 memo에 저장하고 재사용한다.

class Solution:
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        memo = {}

        def dfs(i):
            # 1) base case는 항상 최상단
            if i <= 1:
                return 0

            # 2) 이미 계산된 값이면 바로 반환
            if i in memo:
                return memo[i]

            # 3) 계산 후 memo에 저장
            memo[i] = min(
                dfs(i - 1) + cost[i - 1],
                dfs(i - 2) + cost[i - 2]
            )
            return memo[i]

        return dfs(n)

 중복 계산이 사라져서 빠르다.

• 시간복잡도: O(n) (각 i를 한 번씩만 계산)
• 공간복잡도: O(n) (memo + 재귀 스택)

3) DP Bottom-up (반복문)으로 바꾸기

핵심

Top-down은 “위에서 아래로(재귀)”

Bottom-up은 “아래에서 위로(반복문)”로 dp 테이블을 채운다.

여기서 가장 많이 헷갈렸던 포인트:

cost 길이가 n이면 top은 n이므로 dp[n]을 구해야 한다.

그래서 dp 배열은 n개가 아니라 n+1개가 필요하다.

dp[i] = i번째 위치(0..n)에 도달하는 최소 비용

초기값:

• dp[0] = 0, dp[1] = 0

class Solution:
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        dp = [0] * (n + 1)   # 0..n까지 필요 (top이 n)

        dp[0] = 0
        dp[1] = 0

        for i in range(2, n + 1):
            dp[i] = min(
                dp[i - 1] + cost[i - 1],
                dp[i - 2] + cost[i - 2]
            )

        return dp[n]

• 시간복잡도: O(n)
• 공간복잡도: O(n)

1. 문제

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Example 1:

Input: rooms = [[1],[2],[3],[]]

Output: true

Explanation: 

We visit room 0 and pick up key 1.

We then visit room 1 and pick up key 2.

We then visit room 2 and pick up key 3.

We then visit room 3.

Since we were able to visit every room, we return true.

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]]

Output: false

Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Constraints:

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n

 • All the values of rooms[i] are unique.

https://leetcode.com/problems/keys-and-rooms/description/

2. 첫 접근: 딕셔너리 + DFS

처음에는 문제를 이렇게 해석했다.

방 번호 → 그 방에서 갈 수 있는 방 목록

⇒ 딕셔너리로 매핑하면 좋겠다

그래서 다음과 같은 구조로 시작했다.

class Solution():
    def canVisitAllRooms(self, rooms):
        dic_rooms = {}
        for i, r in enumerate(rooms):
            dic_rooms[i] = r

        visited = []

        def dfs(cur_r):
            for k in dic_rooms[cur_r]:
                if k not in visited:
                    if cur_r not in visited:
                        visited.append(cur_r)
                    visited.append(k)
                    dfs(k)

        dfs(0)

        return len(visited) == len(rooms)

• DFS 개념은 맞음
• 문제를 “그래프 탐색”으로 이해한 건 정확함

3. 문제점 발견

❌ 1) 딕셔너리가 사실 필요 없음

문제에서 주어진 rooms 자체가 이미 이런 구조였다.

rooms[i] = i번 방에서 갈 수 있는 방 목록
즉, dic_rooms[i] = rooms[i]를 따로 만들 이유가 없었다.

❌ 2) visited를 리스트로 사용

if k not in visited:

이 부분은 O(n) 이 걸린다.

DFS 중에 이 검사가 반복되면 전체 시간복잡도가 O(n²) 까지 늘어날 수 있다.

그래프 문제에서 이건 코테 기준으로 비효율적이다.

4. 개선 방향 정리

1. rooms 자체를 그래프(인접 리스트)로 사용
2. visited는 반드시 set 사용
3. 방문 처리는 “노드에 들어오는 순간” 한 번만

5. 최종 해결: set + DFS (정석 풀이)

class Solution():
    def canVisitAllRooms(self, rooms):
        visited = set()

        def dfs(cur_r):
            visited.add(cur_r)
            for k in rooms[cur_r]:
                if k not in visited:
                    dfs(k)

        dfs(0)
        return len(visited) == len(rooms)

5-1. set + BFS

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms):
        visited = set()
        q = deque([0])   # 시작 방
        visited.add(0)

        while q:
            cur = q.popleft()
            for nxt in rooms[cur]:
                if nxt not in visited:
                    visited.add(nxt)
                    q.append(nxt)

        return len(visited) == len(rooms)

6. 시간복잡도 분석

• 각 방(노드): 최대 1번 방문 → O(V)
• 각 열쇠(간선): 최대 1번 확인 → O(E)

전체 시간복잡도

O(V + E)