sladuf
200
sladuf
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (83)
    • ๐Ÿ“š Programming (32)
      • Swift (13)
      • JAVA (2)
      • Python (6)
      • SQL (6)
      • Web (5)
    • ๐Ÿ“ฑ iOS (25)
      • Base (7)
      • SwiftUI (9)
      • UIKit (7)
      • ์ธ๊ฐ• & ์ฑ… (2)
    • ๐Ÿ”— Algorithm (20)
      • Python (12)
      • Swift (3)
      • Tip (5)
    • ๐Ÿ—‚ ETC (6)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

ํƒœ๊ทธ

  • ์Šค์œ„ํ”„ํŠธ
  • Swift

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๊ธ€์“ฐ๊ธฐ ์„ค์ •
hELLO ยท Designed By ์ •์ƒ์šฐ.
sladuf

200

[Python] ๋ฐฑ์ค€ 2606
๐Ÿ”— Algorithm/Python

[Python] ๋ฐฑ์ค€ 2606

2020. 9. 1. 17:07

 

 

 

 

BFS๋˜๋Š” DFS๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ๋ฌธ์ œ๋‹ค.

 

 

๋จผ์ €, ์ž…๋ ฅ๋ฐ›์€ ๋ฐ์ดํ„ฐ๋Š” ๋”•์…”๋„ˆ๋ฆฌ๋กœ ๊ตฌํ˜„ํ•˜์˜€๋‹ค.

๋„คํŠธ์›Œํฌ๋Š” ์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„ ์ด๋ฏ€๋กœ ์•„๋ž˜ ์ฝ”๋“œ์™€ ๊ฐ™์ด ๋”•์…”๋„ˆ๋ฆฌ์— ๋‘ ๋ฒˆ ์ž…๋ ฅํ•ด์•ผ ํ•œ๋‹ค. 

 

 

๊ทธ๋ž˜ํ”„ ๊ตฌํ˜„

net = {}

for i in range(n):
    a, b = map(int, input().split())
    if a in net :
        net[a].append(b)
    else : 
        net[a] = [b]
    if b in net :
        net[b].append(a)
    else :
        net[b] = [a]

 

 

 

๊ฐ™์€ ๋„คํŠธ์›Œํฌ ์ƒ์— ์žˆ๋Š” ์ปดํ“จํ„ฐ๋ฅผ ๊ฒ€์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ BFS๋ฅผ ์‚ฌ์šฉํ–ˆ๋‹ค.

visit์—์„œ 1์„ ๋นผ๋ฉด 1๊ณผ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ปดํ“จํ„ฐ๋งŒ ๋‚จ๊ฒŒ ๋˜๊ธฐ ๋•Œ๋ฌธ์— len(visit)-1์„ ๊ฒฐ๊ณผ๋กœ ์ถœ๋ ฅํ–ˆ๋‹ค.

 

 

์ „์ฒด์ฝ”๋“œ

m = int(input())
n = int(input())

net = {}

for i in range(n):
    a, b = map(int, input().split())
    if a in net :
        net[a].append(b)
    else : 
        net[a] = [b]
    if b in net :
        net[b].append(a)
    else :
        net[b] = [a]
        
queue = [1]
visit = []

while queue :
    temp = queue.pop(0)
    if temp not in visit :
        visit.append(temp)
        queue.extend(net[temp])

print(len(visit)-1)

 

 

 

 

 

์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'๐Ÿ”— Algorithm > Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[Python] ๋ฐฑ์ค€ 2089  (0) 2021.03.04
[Python] ๋ฐฑ์ค€ 1442  (0) 2021.02.25
[Python] ๋ฐฑ์ค€ 6549  (0) 2021.02.20
[Python] ๋ฐฑ์ค€ 1260  (0) 2020.08.27
[Python] ๋ฐฑ์ค€ 2231  (0) 2020.05.03
    '๐Ÿ”— Algorithm/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [Python] ๋ฐฑ์ค€ 1442
    • [Python] ๋ฐฑ์ค€ 6549
    • [Python] ๋ฐฑ์ค€ 1260
    • [Python] ๋ฐฑ์ค€ 2231
    sladuf
    sladuf

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”