๐Ÿ’ป Algorithm/Python

[Python] ๋ฐฑ์ค€ 1012 ์œ ๊ธฐ๋† ๋ฐฐ์ถ” (BFS)

์„ ์ฃผ 2022. 7. 8. 19:44

๐Ÿ“Œ ๋ฌธ์ œ

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

 

ํ•œ๋‚˜๊ฐ€ ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋Š” ๋•…์€ ๊ณ ๋ฅด์ง€ ๋ชปํ•ด์„œ ๋ฐฐ์ถ”๋ฅผ ๊ตฐ๋ฐ๊ตฐ๋ฐ ์‹ฌ์–ด ๋†“์•˜๋‹ค. ๋ฐฐ์ถ”๋“ค์ด ๋ชจ์—ฌ์žˆ๋Š” ๊ณณ์—๋Š” ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋งŒ ์žˆ์œผ๋ฉด ๋˜๋ฏ€๋กœ ์„œ๋กœ ์ธ์ ‘ํ•ด์žˆ๋Š” ๋ฐฐ์ถ”๋“ค์ด ๋ช‡ ๊ตฐ๋ฐ์— ํผ์ ธ์žˆ๋Š”์ง€ ์กฐ์‚ฌํ•˜๋ฉด ์ด ๋ช‡ ๋งˆ๋ฆฌ์˜ ์ง€๋ ์ด๊ฐ€ ํ•„์š”ํ•œ์ง€ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๋ฐฐ์ถ”๋ฐญ์ด ์•„๋ž˜์™€ ๊ฐ™์ด ๊ตฌ์„ฑ๋˜์–ด ์žˆ์œผ๋ฉด ์ตœ์†Œ 5๋งˆ๋ฆฌ์˜ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•„์š”ํ•˜๋‹ค. 0์€ ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ์ง€ ์•Š์€ ๋•…์ด๊ณ , 1์€ ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ๋Š” ๋•…์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.

 

์ž…๋ ฅ

์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ ๊ฐ๊ฐ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ์ฒซ์งธ ์ค„์—๋Š” ๋ฐฐ์ถ”๋ฅผ ์‹ฌ์€ ๋ฐฐ์ถ”๋ฐญ์˜ ๊ฐ€๋กœ๊ธธ์ด M(1 ≤ M ≤ 50)๊ณผ ์„ธ๋กœ๊ธธ์ด N(1 ≤ N ≤ 50), ๊ทธ๋ฆฌ๊ณ  ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ๋Š” ์œ„์น˜์˜ ๊ฐœ์ˆ˜ K(1 ≤ K ≤ 2500)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ K์ค„์—๋Š” ๋ฐฐ์ถ”์˜ ์œ„์น˜ X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘ ๋ฐฐ์ถ”์˜ ์œ„์น˜๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” ์—†๋‹ค.

์ถœ๋ ฅ

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ์˜ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด ๋งˆ๋ฆฌ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

์˜ˆ์ œ ์ถœ๋ ฅ 1

5
1

์˜ˆ์ œ ์ž…๋ ฅ 2

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

์˜ˆ์ œ ์ถœ๋ ฅ 2

2

 


๐Ÿ“Œ ํ’€์ด

๐Ÿ’ฌ Code

import sys
from collections import deque
input = sys.stdin.readline


def bfs(x, y):
    q = deque([(x, y)])
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                q.append((nx, ny))
                graph[nx][ny] = 2
    return 1


for _ in range(int(input())):
    m, n, k = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(n)]

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(k):
        a, b = map(int, input().split())
        graph[b][a] = 1

    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                cnt += bfs(i, j)

    print(cnt)

๐Ÿ’ก Solution

cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            cnt += bfs(i, j)

๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ง„ ๊ณณ์—์„œ bfs๋ฅผ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค. bfs๋Š” ์ธ์ ‘ํ•œ ๋ฐฐ์ถ”๋ฅผ ๋‹ค ์ฒดํฌํ•˜๊ณ  1์„ ๋ฐ˜ํ™˜ํ•˜๋„๋ก ์„ค๊ณ„๋˜์–ด ์žˆ์–ด์„œ, cnt += bfs(i, j)๋Š” ๋ฐฐ์ถ”๊ตฌ์—ญ ํ•˜๋‚˜๋ฅผ ์ฒดํฌํ•  ๋•Œ๋งˆ๋‹ค ์ง€๋ ์ด ํ•œ ๋งˆ๋ฆฌ๋ฅผ ๋”ํ•˜๋Š” ์—ญํ• ์„ ํ•ฉ๋‹ˆ๋‹ค.

def bfs(x, y):
    q = deque([(x, y)])
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                q.append((nx, ny))
                graph[nx][ny] = 2
    return 1

๋ฐฐ์ถ” ์ขŒํ‘œ (x, y)๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ํ•ด๋‹น ๋ฐฐ์ถ”์™€ ์ธ์ ‘ํ•œ ๋ฐฐ์ถ”๋ฅผ ์‚ดํŽด๋ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋ฐฉํ–ฅ๋ฒกํ„ฐ๋กœ ์ƒํ•˜์ขŒ์šฐ์˜ ๋„ค ์œ„์น˜๋กœ ์ด๋™ํ•˜๊ธฐ ์œ„ํ•ด for๋ฌธ์„ ๋„ค ๋ฒˆ ๋Œ๋ฆฝ๋‹ˆ๋‹ค. (nx, ny)๋Š” ํ•ด๋‹น ๋ฐฉํ–ฅ์œผ๋กœ ํ•œ ์นธ ์ด๋™ํ•œ ์ขŒํ‘œ์ž…๋‹ˆ๋‹ค. (nx, ny)๊ฐ€ ์ขŒํ‘œ๊ณ„๋ฅผ ๋ฒ—์–ด๋‚˜์ง€ ์•Š์•˜์Œ๊ณผ ๋™์‹œ์— ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ง„ ์ขŒํ‘œ๋ผ๋ฉด ์ด ์ขŒํ‘œ์˜ ์ธ์ ‘ ๋ฐฐ์ถ”๋ฅผ ๋˜ ํƒ์ƒ‰ํ•˜๊ธฐ ์œ„ํ•ด ํ์— ๋„ฃ์Šต๋‹ˆ๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ (nx, ny)๋ฅผ ์ฒดํฌํ–ˆ๋‹ค๋Š” ๋œป์—์„œ ์ขŒํ‘œ๊ฐ’์„ 2๋กœ ๋ณ€๊ฒฝํ•ฉ๋‹ˆ๋‹ค.

 

bfs๊ฐ€ ํ•œ ๋ฒˆ ๋๋‚˜๋ฉด ์‹œ์ž‘์ขŒํ‘œ์™€ ์ธ์ ‘ํ•œ ๋ฐฐ์ถ”๋“ค์˜ ์ขŒํ‘œ๊ฐ’์—๋Š” ๋ชจ๋‘ 2๊ฐ€ ๋ฎ์–ด์”Œ์›Œ์ง€๊ณ , ๊ตฌ์—ญ 1๊ฐœ๋ฅผ ๋‹ค ์‚ดํŽด๋ณด์•˜๋‹ค๋Š” ์˜๋ฏธ๋กœ 1์„ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.