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

2021. 1. 12. 21:33ใ†๐Ÿ“š Algorithm/๐Ÿ’ช๐Ÿป Python ๋ฌธ์ œ ํ’€์ด

๋ฐ˜์‘ํ˜•
 

1012๋ฒˆ: ์œ ๊ธฐ๋† ๋ฐฐ์ถ”

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

www.acmicpc.net

๋ฌธ์ œ ์„ค๋ช…

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

(ํ•œ ๋ฐฐ์ถ”์˜ ์ƒํ•˜์ขŒ์šฐ ๋„ค ๋ฐฉํ–ฅ์— ๋‹ค๋ฅธ ๋ฐฐ์ถ”๊ฐ€ ์œ„์น˜ํ•œ ๊ฒฝ์šฐ์— ์„œ๋กœ ์ธ์ ‘ํ•ด์žˆ๋‹ค๊ณ  ๊ฐ„์ฃผํ•œ๋‹ค)

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

์˜ˆ๋ฅผ ๋“ค์–ด ๋ฐฐ์ถ”๋ฐญ์ด ์•„๋ž˜์™€ ๊ฐ™์ด ๊ตฌ์„ฑ๋˜์–ด ์žˆ์œผ๋ฉด ์ตœ์†Œ 5๋งˆ๋ฆฌ์˜ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•„์š”ํ•˜๋‹ค.

(0์€ ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ์ง€ ์•Š์€ ๋•…์ด๊ณ , 1์€ ๋ฐฐ์ถ”๊ฐ€ ์‹ฌ์–ด์ ธ ์žˆ๋Š” ๋•…์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.)

1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 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)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅํ˜•์‹

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

์ž…์ถœ๋ ฅ ์˜ˆ์‹œ

 

ํ’€์ด ๊ณผ์ •

BFS ๋ฌธ์ œ๋ฅผ ๊ณ„์† ํ’€๋‹ค๋ณด๋‹ˆ ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์ด ๋งค์šฐ ๋น„์Šทํ•˜๋‹ค๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ์—ˆ๋‹ค.

์•„๋ž˜ ๋‹จ์ง€๋ฒˆํ˜ธ ๋ถ™์ด๊ธฐ์™€ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ํ’€๊ฒŒ ๋˜์—ˆ๋‹ค. ์ƒํ•˜์ขŒ์šฐ๋ฅผ ๊ฒ€์‚ฌํ•˜์—ฌ ๊ฐ™์€ ๊ฐ’์ด ์กด์žฌํ•˜๋ฉด queue์— ๋„ฃ์–ด ๋ชจ๋‘ ๊ฒ€์‚ฌํ•˜๋„๋ก ๊ตฌํ˜„ํ•œ๋’ค 1์„ return ํ•ด์ฃผ์—ˆ๋‹ค.

 

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

๊ณผ ๊ฐ™์ด ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ์ง€๋„๊ฐ€ ์žˆ๋‹ค. 1์€ ์ง‘์ด ์žˆ๋Š” ๊ณณ์„, 0์€ ์ง‘์ด ์—†๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ฒ ์ˆ˜๋Š” ์ด ์ง€๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์—ฐ๊ฒฐ๋œ ์ง‘์˜ ๋ชจ์ž„์ธ ๋‹จ์ง€๋ฅผ ์ •์˜ํ•˜๊ณ , ๋‹จ์ง€์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ด๋ ค ํ•œ๋‹ค. ์—ฌ" data-og-h

yunaaaas.tistory.com

import sys
from collections import deque


def bfs(x, y):
    dxy = [(0, 1), (-1, 0), (0, -1), (1, 0)]
    queue = deque([(x, y)])
    while queue:
        item = queue.popleft()
        for xy in dxy:
            new_x = int(item[0] + xy[0])
            new_y = int(item[1] + xy[1])
            if 0 <= new_x < m and 0 <= new_y < n and check[new_x][new_y] != 1:
                if maps[new_x][new_y] == maps[item[0]][item[1]]:
                    queue.append((new_x, new_y))
                    check[new_x][new_y] = 1

    return 1


number = int(input())
for _ in range(number):
    m, n, k = map(int, sys.stdin.readline().split())
    maps = [[0 for _ in range(n)] for _ in range(m)]
    check = [[0 for _ in range(n)] for _ in range(m)]
    answer = 0
    for _ in range(k):
        i, j = map(int,sys.stdin.readline().split())
        maps[i][j] = 1

    for i in range(m):
        for j in range(n):
            if maps[i][j] != 0:
                if check[i][j] != 1:
                    answer += bfs(i, j)

    print(answer)

 

 

 

๋ฐ˜์‘ํ˜•