๐Ÿฆ  ๋ฐ”์ด๋Ÿฌ์Šค

๋ฐฑ์ค€ Class3 Silver3

solved_ac[Class3] ๋ฐ”์ด๋Ÿฌ์Šค

๋ฌธ์ œ

์‹ ์ข… ๋ฐ”์ด๋Ÿฌ์Šค์ธ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” ๋„คํŠธ์›Œํฌ๋ฅผ ํ†ตํ•ด ์ „ํŒŒ๋œ๋‹ค. ํ•œ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๋ฉด ๊ทธ ์ปดํ“จํ„ฐ์™€ ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋ชจ๋“  ์ปดํ“จํ„ฐ๋Š” ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด 7๋Œ€์˜ ์ปดํ“จํ„ฐ๊ฐ€ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ™์ด ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๊ณ  ํ•˜์ž. 1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๋ฉด ์›œ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” 2๋ฒˆ๊ณผ 5๋ฒˆ ์ปดํ“จํ„ฐ๋ฅผ ๊ฑฐ์ณ 3๋ฒˆ๊ณผ 6๋ฒˆ ์ปดํ“จํ„ฐ๊นŒ์ง€ ์ „ํŒŒ๋˜์–ด 2, 3, 5, 6 ๋„ค ๋Œ€์˜ ์ปดํ“จํ„ฐ๋Š” ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค. ํ•˜์ง€๋งŒ 4๋ฒˆ๊ณผ 7๋ฒˆ ์ปดํ“จํ„ฐ๋Š” 1๋ฒˆ ์ปดํ“จํ„ฐ์™€ ๋„คํŠธ์›Œํฌ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ์˜ํ–ฅ์„ ๋ฐ›์ง€ ์•Š๋Š”๋‹ค.

img

์–ด๋Š ๋‚  1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ ธ๋‹ค. ์ปดํ“จํ„ฐ์˜ ์ˆ˜์™€ ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ •๋ณด๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, 1๋ฒˆ ์ปดํ“จํ„ฐ๋ฅผ ํ†ตํ•ด ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋˜๋Š” ์ปดํ“จํ„ฐ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์—๋Š” ์ปดํ“จํ„ฐ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ปดํ“จํ„ฐ์˜ ์ˆ˜๋Š” 100 ์ดํ•˜์ด๊ณ  ๊ฐ ์ปดํ“จํ„ฐ์—๋Š” 1๋ฒˆ ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์ง์ ‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ปดํ“จํ„ฐ ์Œ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด์–ด์„œ ๊ทธ ์ˆ˜๋งŒํผ ํ•œ ์ค„์— ํ•œ ์Œ์”ฉ ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์ง์ ‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ปดํ“จํ„ฐ์˜ ๋ฒˆํ˜ธ ์Œ์ด ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ ธ์„ ๋•Œ, 1๋ฒˆ ์ปดํ“จํ„ฐ๋ฅผ ํ†ตํ•ด ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋˜๋Š” ์ปดํ“จํ„ฐ์˜ ์ˆ˜๋ฅผ ์ฒซ์งธ ์ค„์— ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

7
6
1 2
2 3
1 5
5 2
5 6
4 7

์˜ˆ์ œ ์ถœ๋ ฅ 1

4

๐Ÿ›  ์ž๋ฃŒ๊ตฌ์กฐ

์ด ๋ฌธ์ œ๋Š” DFS, BFS ์–ด๋–ค ๊ฒƒ์„ ์„ ํƒํ•˜์—ฌ ํ’€๋“  ๋ฌด๋ฐฉํ•˜๋‹ค. ์™œ๋ƒํ•˜๋ฉด ๊ทธ๋ž˜ํ”„ ์ „์ฒด๋ฅผ ์ˆœํšŒํ•˜๋ฉฐ ํƒ์ƒ‰ํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ๋‚˜๋Š” BFS๊ฐ€ ์กฐ๊ธˆ ๋” ์ต์ˆ™ํ•˜์—ฌ BFS๋กœ ํ’€์—ˆ๋‹ค.

BFS ๊ธฐ๋ณธ ๊ณจ๊ฒฉ์— count ๋ณ€์ˆ˜(๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฐ ์ปดํ“จํ„ฐ ๊ฐœ์ˆ˜)๋งŒ ์ถ”๊ฐ€ํ•˜์˜€๋‹ค.

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป CODE

from collections import deque
node = int(input())
edge = int(input())

# ์ปดํ“จํ„ฐ ์—ฐ๊ฒฐ๋ง ์ดˆ๊ธฐํ™”
graph = [[0]*(node+1) for _ in range(node+1)]
visited = [0]*(node+1)

# ์ปดํ“จํ„ฐ ์—ฐ๊ฒฐ๋ง ์ƒํƒœ ํ‘œ์‹œ
for _ in range(edge):
    start,end = map(int,input().split())

    graph[start][end] = 1
    graph[end][start] = 1

# ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰
def bfs(start):
    q =deque([start])
    visited[start] = 1
    count = 0

    while q:
        cur = q.popleft()

        for i in range(node+1):
            if graph[cur][i] == 1 and visited[i] == 0:
                q.append(i)
                visited[i] = 1
                count += 1
    
    return count

print(bfs(1))

ยฉ 2022. All rights reserved.

Powered by Hydejack v9.1.6