PS

[๋ฐฑ์ค€] 2636 ์น˜์ฆˆ with Python

ํ˜•์ค€_It's 2022. 3. 18. 17:58
728x90
๋ฐ˜์‘ํ˜•

๐Ÿ“Œ BOJ 2636 ์น˜์ฆˆ

๐Ÿ’ก ์กฐ๊ฑด

  1. ์ •์‚ฌ๊ฐํ˜• ์นธ๋“ค๋กœ ์ด๋ฃจ์–ด์ง„ ์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ํŒ์ด ์žˆ๊ณ , ๊ทธ ์œ„์— ์–‡์€ ์น˜์ฆˆ๊ฐ€ ๋†“์—ฌ ์žˆ๋‹ค.

  2. ์น˜์ฆˆ๋ฅผ ๊ณต๊ธฐ ์ค‘์— ๋†“์œผ๋ฉด ๋…น๊ฒŒ ๋˜๋Š”๋ฐ ๊ณต๊ธฐ์™€ ์ ‘์ด‰๋œ ์นธ์€ ํ•œ ์‹œ๊ฐ„์ด ์ง€๋‚˜๋ฉด ๋…น์•„ ์—†์–ด์ง„๋‹ค.
    ์น˜์ฆˆ์˜ ๊ตฌ๋ฉ ์†์—๋Š” ๊ณต๊ธฐ๊ฐ€ ์—†์ง€๋งŒ ๊ตฌ๋ฉ์„ ๋‘˜๋Ÿฌ์‹ผ ์น˜์ฆˆ๊ฐ€ ๋…น์•„์„œ ๊ตฌ๋ฉ์ด ์—ด๋ฆฌ๋ฉด ๊ตฌ๋ฉ ์†์œผ๋กœ ๊ณต๊ธฐ๊ฐ€ ๋“ค์–ด๊ฐ€๊ฒŒ ๋œ๋‹ค.

  3. ์ž…๋ ฅ์œผ๋กœ ์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ํŒ์˜ ํฌ๊ธฐ์™€ ํ•œ ์กฐ๊ฐ์˜ ์น˜์ฆˆ๊ฐ€ ํŒ ์œ„์— ์ฃผ์–ด์กŒ์„ ๋•Œ,
    ๊ณต๊ธฐ ์ค‘์—์„œ ์น˜์ฆˆ๊ฐ€ ๋ชจ๋‘ ๋…น์•„ ์—†์–ด์ง€๋Š” ๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„๊ณผ ๋ชจ๋‘ ๋…น๊ธฐ ํ•œ ์‹œ๊ฐ„ ์ „์— ๋‚จ์•„์žˆ๋Š” ์น˜์ฆˆ์กฐ๊ฐ์ด ๋†“์—ฌ ์žˆ๋Š” ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ

  4. ์„ธ๋กœ์™€ ๊ฐ€๋กœ์˜ ๊ธธ์ด๋Š” ์ตœ๋Œ€ 100์ด๋‹ค.

  5. ์น˜์ฆˆ๊ฐ€ ์—†๋Š” ์นธ์€ 0, ์น˜์ฆˆ๊ฐ€ ์žˆ๋Š” ์นธ์€ 1๋กœ ์ฃผ์–ด์ง€๋ฉฐ ๊ฐ ์ˆซ์ž ์‚ฌ์ด์—๋Š” ๋นˆ์นธ์ด ํ•˜๋‚˜์”ฉ ์žˆ๋‹ค.

  6. ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰, BFS ์œ ํ˜•์˜ ๋ฌธ์ œ

๐Ÿ–ฅ ์†Œ์Šค ์ฝ”๋“œ

from collections import deque
from sys import stdin

n, m = map(int, stdin.readline().split())
board = []
for _ in range(n):
    board.append(list(map(int, stdin.readline().split())))
dx, dy = [1, 0, 0, -1], [0, 1, -1, 0]
ans = 0
cnt = 0


def melt():
    cnt = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == -1:
                cnt += 1
                board[i][j] = 0
    return cnt


def bfs():
    global ans, cnt
    q = deque()
    q.append((0, 0))
    visited = set()
    visited.add((0, 0))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y

            if -1 < nx < n and -1 < ny < m:
                if (nx, ny) not in visited:
                    if board[nx][ny] == 0:
                        q.append((nx, ny))
                        visited.add((nx, ny))
                    elif board[nx][ny] == 1:
                        board[nx][ny] = -1

    melt_cnt = melt()
    if melt_cnt != 0:
        cnt = melt_cnt
    else:
        print(ans)
        print(cnt)
        exit()


while 1:
    bfs()
    ans += 1

๐Ÿ”– ์˜ˆ์ œ ๋ฐ ์‹คํ–‰๊ฒฐ๊ณผ

์˜ˆ์ œ

13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

์‹คํ–‰๊ฒฐ๊ณผ

3
5

โŒจ๏ธ ๋ฌธ์ œ ํ’€์ด

  1. BFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜์—ฌ ์ขŒํ‘œ ์ด๋™์„ ํ•˜๋ฉฐ ๋นˆ๊ณต๊ฐ„๊ณผ ์น˜์ฆˆ๋ฅผ ์ž…๋ ฅ๋ฐ›์€ board ์—์„œ ์น˜์ฆˆ๋ฅผ ์ฐพ์•„ ํ‘œ์‹œ๋ฅผ ํ•œ ๋’ค, ๋…น์•˜๋‹ค๊ณ  ์ฒ˜๋ฆฌํ•˜๋Š” ๊ฒƒ์ด ๋ชฉํ‘œ์ž…๋‹ˆ๋‹ค.
    ์น˜์ฆˆ๊ฐ€ ๋ชจ๋‘ ๋…น์„ ๋•Œ๊นŒ์ง€ BFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ˜ธ์ถœํ•ด์•ผํ•˜๊ธฐ์— while ๋กœ ํ˜ธ์ถœํ•ด์ฃผ๋ฉด์„œ ํ˜ธ์ถœํ•œ ํšŸ์ˆ˜๋ฅผ ans์— ์ €์žฅํ•ด์ค๋‹ˆ๋‹ค.

  2. ์ด ๋ฌธ์ œ๋Š” ์น˜์ฆˆ ์œ„๋ฅผ ๊ฑท๋Š” ๋А๋‚Œ์ด ์•„๋‹Œ, ๋นˆ ๊ณต๊ฐ„์„ ๊ฑธ์œผ๋ฉด์„œ ์น˜์ฆˆ๊ฐ€ ์žˆ๋Š” ๊ณณ์„ ํ‘œ์‹œํ•˜์—ฌ ์ฒ˜๋ฆฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

  3. (2)๋ฒˆ๊ณผ ๊ฐ™์ด ์ฒ˜๋ฆฌํ•˜์ง€ ์•Š์œผ๋ฉด ์น˜์ฆˆ์˜ ๊ฒ‰๋งŒ ์ฒดํฌํ•ด์ค„ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

  4. ์ฒดํฌ๋œ ์น˜์ฆˆ๋ฅผ ๋…น์ด๋Š” ํ•จ์ˆ˜์ธ melt() ๋ฅผ ์ •์˜ํ•˜์—ฌ ํ˜ธ์ถœํ–ˆ์Šต๋‹ˆ๋‹ค.

  5. melt() ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๊ณ  ๋ฐ˜ํ™˜๋ฐ›์€ ๊ฐ’์€ ์น˜์ฆˆ๊ฐ€ ๋…น์€ ๊ฐœ์ˆ˜์ž…๋‹ˆ๋‹ค.
    ๋ชจ๋‘ ๋…น๊ธฐ ํ•œ์‹œ๊ฐ„ ์ „์— ์น˜์ฆˆ๊ฐ€ ๋…น์€ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•ด์•ผํ•˜๋‹ˆ, ๋ฐ˜ํ™˜๋œ ๊ฐ’์„ cnt ๋ผ๋Š” ๋ณ€์ˆ˜์— ์ €์žฅํ•ด์ค๋‹ˆ๋‹ค.

  6. ๋…น์ง€ ์•Š์•˜๋‹ค๋ฉด ๊ทธ๋Œ€๋กœ ans, cnt ๋ฅผ ์ถœ๋ ฅํ•ด์ค๋‹ˆ๋‹ค.

๐Ÿ’พ ๋А๋‚€์ 

  1. ๋นˆ๊ณต๊ฐ„์„ ๊ฑธ์œผ๋ฉฐ ์น˜์ฆˆ์˜ ๋ฒฝ๋ฉด์„ ํ›‘๋Š”๋‹ค๋Š” ๋А๋‚Œ์„ ์–ป๊ธฐ ์–ด๋ ค์› ๋‹ค.
๋ฐ˜์‘ํ˜•