๋‚ด ์ธ์ƒ์—์„œ ๋ฏฟ์„ ๊ฑด ์˜ค์ง ๋‚˜ ์ž์‹ ๋ฟ!

The only one you can truly trust is yourself.

๊ฒŒ์ž„ ํ”„๋กœ๊ทธ๋ž˜๋ฐ/Python ํ”„๋กœ๊ทธ๋ž˜๋ฐ

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ๋ถ€๋Œ€๋ณต๊ท€ (๊ทธ๋ž˜ํ”„/BFS/์—ญ์ˆœ)

๐ŸŽฎinspirer9 2023. 3. 6. 18:46
728x90
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ ์„ค๋ช…

๊ฐ•์ฒ ๋ถ€๋Œ€์˜ ๊ฐ ๋ถ€๋Œ€์›์ด ์—ฌ๋Ÿฌ ์ง€์—ญ์— ๋ฟ”๋ฟ”์ด ํฉ์–ด์ ธ ํŠน์ˆ˜ ์ž„๋ฌด๋ฅผ ์ˆ˜ํ–‰ ์ค‘์ž…๋‹ˆ๋‹ค. ์ง€๋„์—์„œ ๊ฐ•์ฒ ๋ถ€๋Œ€๊ฐ€ ์œ„์น˜ํ•œ ์ง€์—ญ์„ ํฌํ•จํ•œ ๊ฐ ์ง€์—ญ์€ ์œ ์ผํ•œ ๋ฒˆํ˜ธ๋กœ ๊ตฌ๋ถ„๋˜๋ฉฐ, ๋‘ ์ง€์—ญ ๊ฐ„์˜ ๊ธธ์„ ํ†ต๊ณผํ•˜๋Š” ๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์€ ๋ชจ๋‘ 1๋กœ ๋™์ผํ•ฉ๋‹ˆ๋‹ค. ์ž„๋ฌด๋ฅผ ์ˆ˜ํ–‰ํ•œ ๊ฐ ๋ถ€๋Œ€์›์€ ์ง€๋„ ์ •๋ณด๋ฅผ ์ด์šฉํ•˜์—ฌ ์ตœ๋‹จ์‹œ๊ฐ„์— ๋ถ€๋Œ€๋กœ ๋ณต๊ท€ํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค. ๋‹ค๋งŒ ์ ๊ตฐ์˜ ๋ฐฉํ•ด๋กœ ์ธํ•ด, ์ž„๋ฌด์˜ ์‹œ์ž‘ ๋•Œ์™€ ๋‹ค๋ฅด๊ฒŒ ๋˜๋Œ์•„์˜ค๋Š” ๊ฒฝ๋กœ๊ฐ€ ์—†์–ด์ ธ ๋ณต๊ท€๊ฐ€ ๋ถˆ๊ฐ€๋Šฅํ•œ ๋ถ€๋Œ€์›๋„ ์žˆ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๊ฐ•์ฒ ๋ถ€๋Œ€๊ฐ€ ์œ„์น˜ํ•œ ์ง€์—ญ์„ ํฌํ•จํ•œ ์ด์ง€์—ญ์˜ ์ˆ˜ n, ๋‘ ์ง€์—ญ์„ ์™•๋ณตํ•  ์ˆ˜ ์žˆ๋Š” ๊ธธ ์ •๋ณด๋ฅผ ๋‹ด์€ 2์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด roads, ๊ฐ ๋ถ€๋Œ€์›์ด ์œ„์น˜ํ•œ ์„œ๋กœ ๋‹ค๋ฅธ ์ง€์—ญ๋“ค์„ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ ๋ฐฐ์—ด sources, ๊ฐ•์ฒ ๋ถ€๋Œ€์˜ ์ง€์—ญ destination์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฃผ์–ด์ง„ sources์˜ ์›์†Œ ์ˆœ์„œ๋Œ€๋กœ ๊ฐ•์ฒ ๋ถ€๋Œ€๋กœ ๋ณต๊ท€ํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋‹จ์‹œ๊ฐ„์„ ๋‹ด์€ ๋ฐฐ์—ด์„ returnํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”. ๋ณต๊ท€๊ฐ€ ๋ถˆ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ ํ•ด๋‹น ๋ถ€๋Œ€์›์˜ ์ตœ๋‹จ์‹œ๊ฐ„์€ -1์ž…๋‹ˆ๋‹ค.

์ œํ•œ ์‚ฌํ•ญ

  • 3 ≤ n ≤ 100,000
    • ๊ฐ ์ง€์—ญ์€ ์ •์ˆ˜ 1๋ถ€ํ„ฐ n๊นŒ์ง€์˜ ๋ฒˆํ˜ธ๋กœ ๊ตฌ๋ถ„๋ฉ๋‹ˆ๋‹ค.
  • 2 ≤ roads์˜ ๊ธธ์ด ≤ 500,000
    • roads์˜ ์›์†Œ์˜ ๊ธธ์ด = 2
    • roads์˜ ์›์†Œ๋Š” [a, b] ํ˜•ํƒœ๋กœ ๋‘ ์ง€์—ญ a, b๊ฐ€ ์„œ๋กœ ์™•๋ณตํ•  ์ˆ˜ ์žˆ์Œ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.(1 ≤ a, b ≤ n, a ≠ b)
    • ๋™์ผํ•œ ์ •๋ณด๊ฐ€ ์ค‘๋ณตํ•ด์„œ ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
      • ๋™์ผํ•œ [a, b]๊ฐ€ ์ค‘๋ณตํ•ด์„œ ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
      • [a, b]๊ฐ€ ์žˆ๋‹ค๋ฉด [b, a]๋Š” ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • 1 ≤ sources์˜ ๊ธธ์ด ≤ 500
    • 1 ≤ sources[i] ≤ n
  • 1 ≤ destination ≤ n

์ž…์ถœ๋ ฅ ์˜ˆ

n roads sources destination result
3 [[1, 2], [2, 3]] [2, 3] 1 [1, 2]
5 [[1, 2], [1, 4], [2, 4], [2, 5], [4, 5]] [1, 3, 5] 5 [2, -1, 0]

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

  • ์ง€์—ญ 2๋Š” ์ง€์—ญ 1๊ณผ ๊ธธ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์—, ์ง€์—ญ 2์—์„œ ์ง€์—ญ 1์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 1์ž…๋‹ˆ๋‹ค.
  • ์ง€์—ญ 3์—์„œ ์ง€์—ญ 1๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋‹จ๊ฒฝ๋กœ๋Š” ์ง€์—ญ 3 → ์ง€์—ญ 2 → ์ง€์—ญ 1 ์ˆœ์œผ๋กœ ์ด๋™ํ•˜๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์—, ์ง€์—ญ 3์—์„œ ์ง€์—ญ 1์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 2์ž…๋‹ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ [1, 2]๋ฅผ returnํ•ฉ๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

  • ์ง€์—ญ 1์—์„œ ์ง€์—ญ 5์˜ ์ตœ๋‹จ๊ฒฝ๋กœ๋Š” ์ง€์—ญ 1 → ์ง€์—ญ 2 → ์ง€์—ญ 5 ๋˜๋Š” ์ง€์—ญ 1 → ์ง€์—ญ 4 → ์ง€์—ญ 5 ์ˆœ์œผ๋กœ ์ด๋™ํ•˜๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์—, ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 2์ž…๋‹ˆ๋‹ค.
  • ์ง€์—ญ 3์—์„œ ์ง€์—ญ 5๋กœ ๊ฐ€๋Š” ๊ฒฝ๋กœ๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์—, ์ง€์—ญ 3์—์„œ ์ง€์—ญ 5๋กœ ๊ฐ€๋Š” ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” -1์ž…๋‹ˆ๋‹ค.
  • ์ง€์—ญ 5์—์„œ ์ง€์—ญ 5๋Š” ์ด๋™ํ•  ํ•„์š”๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์—, ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 0์ž…๋‹ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ [2, -1, 0]์„ returnํ•ฉ๋‹ˆ๋‹ค.

ํ’€์ด

import collections

def solution(n, roads, sources, destination):
    answer = []
    dp = [-1 for _ in range(n+1)]
    graph = {}
    for r in roads:
        s, e = r
        try:
            graph[s].append(e)
        except:
            graph[s] = [e]
        try:
            graph[e].append(s)
        except:
            graph[e] = [s]
    
    queue = collections.deque()
    queue.append(destination)
    dp[destination] = 0
    
    while queue:
        q = queue.popleft()
        gr = graph[q]
        for g in gr:
            if dp[g] == -1:
                dp[g] = dp[q] + 1
                queue.append(g)
    
    for s in sources:
        answer.append(dp[s])
    
    return list(answer)
    
์ •ํ™•์„ฑ  ํ…Œ์ŠคํŠธ
ํ…Œ์ŠคํŠธ 1 ใ€‰	ํ†ต๊ณผ (0.01ms, 10.3MB)
ํ…Œ์ŠคํŠธ 2 ใ€‰	ํ†ต๊ณผ (0.01ms, 10.1MB)
ํ…Œ์ŠคํŠธ 3 ใ€‰	ํ†ต๊ณผ (0.01ms, 10.3MB)
ํ…Œ์ŠคํŠธ 4 ใ€‰	ํ†ต๊ณผ (0.01ms, 10.2MB)
ํ…Œ์ŠคํŠธ 5 ใ€‰	ํ†ต๊ณผ (0.01ms, 10.2MB)
ํ…Œ์ŠคํŠธ 6 ใ€‰	ํ†ต๊ณผ (16.19ms, 16.1MB)
ํ…Œ์ŠคํŠธ 7 ใ€‰	ํ†ต๊ณผ (18.49ms, 17.2MB)
ํ…Œ์ŠคํŠธ 8 ใ€‰	ํ†ต๊ณผ (28.04ms, 22.1MB)
ํ…Œ์ŠคํŠธ 9 ใ€‰	ํ†ต๊ณผ (8.42ms, 13.8MB)
ํ…Œ์ŠคํŠธ 10 ใ€‰	ํ†ต๊ณผ (9.36ms, 14.4MB)
ํ…Œ์ŠคํŠธ 11 ใ€‰	ํ†ต๊ณผ (675.22ms, 115MB)
ํ…Œ์ŠคํŠธ 12 ใ€‰	ํ†ต๊ณผ (696.34ms, 115MB)
ํ…Œ์ŠคํŠธ 13 ใ€‰	ํ†ต๊ณผ (774.33ms, 116MB)
ํ…Œ์ŠคํŠธ 14 ใ€‰	ํ†ต๊ณผ (690.98ms, 116MB)
ํ…Œ์ŠคํŠธ 15 ใ€‰	ํ†ต๊ณผ (698.60ms, 115MB)
ํ…Œ์ŠคํŠธ 16 ใ€‰	ํ†ต๊ณผ (171.59ms, 45.5MB)

ํ•ด์„ค ๋ณด๊ณ  ํ‘ธ๋‹ˆ๊นŒ ์‰ฌ์šด๋ฐ, ์•ˆ๋ณด๊ณ  ํ’€์—ˆ์œผ๋ฉด ์ด๊ฒƒ๋„ ์‹œ๊ฐ„ ๋‚ญ๋น„ ํ–ˆ์„ ๊ฐ...

728x90
๋ฐ˜์‘ํ˜•