๐Ÿ’ป Algorithm/Python

[Python] ๋ฐฑ์ค€ 2667 ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ (BFS)

์„ ์ฃผ 2022. 7. 2. 15:47

 

๐Ÿ“Œ ๋ฌธ์ œ

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

 

์ž…๋ ฅ

์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์ง€๋„์˜ ํฌ๊ธฐ N(์ •์‚ฌ๊ฐํ˜•์ด๋ฏ€๋กœ ๊ฐ€๋กœ์™€ ์„ธ๋กœ์˜ ํฌ๊ธฐ๋Š” ๊ฐ™์œผ๋ฉฐ 5≤N≤25)์ด ์ž…๋ ฅ๋˜๊ณ , ๊ทธ ๋‹ค์Œ N์ค„์—๋Š” ๊ฐ๊ฐ N๊ฐœ์˜ ์ž๋ฃŒ(0ํ˜น์€ 1)๊ฐ€ ์ž…๋ ฅ๋œ๋‹ค.

์ถœ๋ ฅ

์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์ด ๋‹จ์ง€์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜์‹œ์˜ค. ๊ทธ๋ฆฌ๊ณ  ๊ฐ ๋‹จ์ง€๋‚ด ์ง‘์˜ ์ˆ˜๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ถœ๋ ฅํ•˜์‹œ์˜ค.

์˜ˆ์ œ ์ž…๋ ฅ 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

์˜ˆ์ œ ์ถœ๋ ฅ 1

3
7
8
9

 


 

๐Ÿ“Œ ํ’€์ด

๐Ÿ’ฌ Code

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


def bfs(x, y):
    q = deque([(x, y)])
    cnt = 1

    while q:
        x, y = q.popleft()
        visited[x][y] = 1

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

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and town[nx][ny] == 1:
                town[nx][ny] += 1
                q.append((nx, ny))
                cnt += 1

    count.append(cnt)


if __name__ == '__main__':
    n = int(input())
    town = []

    for _ in range(n):
        town.append(list(map(int, input().rstrip())))

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    visited = [[0 for _ in range(n)] for _ in range(n)]

    count = []

    for i in range(n):
        for j in range(n):
            if not visited[i][j] and town[i][j] == 1:
                bfs(i, j)

    count.sort()
    print(len(count), *count, sep='\n')

๐Ÿ’ก Solution

  • town: ์ง‘์ด ์žˆ๋Š” ๊ณณ๊ณผ ์—†๋Š” ๊ณณ์„ ํ‘œํ˜„ํ•œ ์ง€๋„
  • dx, dy: ๋ฐฉํ–ฅ๋ฒกํ„ฐ (์ƒ, ํ•˜, ์ขŒ, ์šฐ)
  • visited: ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ ๋ฐฉ๋ฌธํ–ˆ๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ๊ธฐ๋กํ•˜๋Š” 2์ฐจ์› ๋ฐฐ์—ด
  • count: ๊ฐ ๋‹จ์ง€์˜ ๊ฐ€๊ตฌ ์ˆ˜๋ฅผ ๋‹ด์•„๋‘๋Š” ๋ฐฐ์—ด
for i in range(n):
    for j in range(n):
        if not visited[i][j] and town[i][j] == 1:
            bfs(i, j)

์œ„ ์ฝ”๋“œ์—์„œ ๋ณผ ์ˆ˜ ์žˆ๋“ฏ (0, 0)๋ถ€ํ„ฐ ์ขŒํ‘œ๋ฅผ ์ฒดํฌํ•ฉ๋‹ˆ๋‹ค. ํ•ด๋‹น ์ขŒํ‘œ์— ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜๊ณ  ์ง‘์ด ์žˆ๋‹ค๋ฉด bfs(0, 0)์„ ํ˜ธ์ถœํ•ฉ๋‹ˆ๋‹ค.

def bfs(x, y):
    q = deque([(x, y)])
    cnt = 1

    while q:
        x, y = q.popleft()
        visited[x][y] = 1

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

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and town[nx][ny] == 1:
                town[nx][ny] += 1
                q.append((nx, ny))
                cnt += 1

    count.append(cnt)

(0, 0)์œผ๋กœ๋ถ€ํ„ฐ ์ƒํ•˜์ขŒ์šฐ๋กœ ์ด๋™ํ•œ ํ›„์˜ ์ขŒํ‘œ๋ฅผ ์ฒดํฌํ•˜๊ธฐ ์œ„ํ•ด for๋ฌธ์„ 4๋ฒˆ ๋Œ๋ฆฝ๋‹ˆ๋‹ค. ์ด๋™ ํ›„ ์ขŒํ‘œ๊ฐ€ ์ขŒํ‘œ๋ฒ”์œ„๋ฅผ ๋„˜์ง€ ์•Š๊ณ , ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜๊ณ , ์ง‘์ด ์žˆ๋‹ค๋ฉด ํ์— ๋„ฃ์Šต๋‹ˆ๋‹ค. ์—ฐ๊ฒฐ๋œ ํ•œ ๊ฐ€๊ตฌ๋ฅผ ์ฐพ์•˜์œผ๋ฏ€๋กœ cnt๋ฅผ 1 ์ฆ๊ฐ€์‹œํ‚ต๋‹ˆ๋‹ค.