🔍 Problem

1012 유기농 배추

📃 Input&Output

📒 해결 과정

1️⃣ 시작 위치를 큐에 넣는다
2️⃣ 큐가 빌 때까지 다음을 반복한다
	➊ 🧺 큐에서 현재 위치를 꺼낸다
	➋ 🔍 현재 위치에서 상, 하, 좌, 우 방향으로 이동 가능한 좌표를 확인한다
	➌ ✅ 이동 가능한 좌표가 있다면, 아래를 수행한다:
		① ➕ 해당 좌표를 큐에 삽입하고 방문처리를 한다.
3️⃣ 📝 큐가 비었으면 현재 영역에 대한 탐색이 끝났으므로 애벌레의 개수를 +1한다.
 
 
 → 📏 위의 내용을 테스트 케이스 만큼 반복한다.

❗주의점

1. 가로 세로에 대한 변수를 M,N으로 설정하는게 익숙하지 않아 문제를 많이 풀어봐야겠다.
2. 큐에 넣는 것이 x,y가 아닌 dx와 dy를 참고하여 이동된 next_x, next_y라는 것을 잊지말자.
3. next_x와 next_y는 0초과가 아니라 이상이라는 점을 잊지말자.
4. next 좌표는 0<= next 좌표 < N or M 이라는 것을 잊지말자.

💻 Code

import sys
from collections import deque


# 큐에 넣은 순간 방문처리!!

N = int(sys.stdin.readline())

mat = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
vst = [[False] * N for _ in range(N)]


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

result = []


def BFS(x, y):
    que = deque([])
    vst_cnt = 0
    que.append((x, y))
    vst[x][y] = True

    while que:
        now_x, now_y = que.popleft()
        vst_cnt += 1

        for i in range(4):
            next_x, next_y = now_x + dx[i], now_y + dy[i]
            if next_x >= 0 and next_y >= 0 and next_x < N and next_y < N:
                if vst[next_x][next_y] == False and mat[next_x][next_y] == 1:
                    que.append((next_x, next_y))
                    vst[next_x][next_y] = True

    result.append(vst_cnt)


for i in range(N):
    for j in range(N):
        if mat[i][j] == 1 and vst[i][j] == False:
            BFS(i, j)


print(len(result))
result.sort()

for i in result:
    print(i)

🤔 느낀점

익숙해졌다 싶으면 잔실수가 나와 시간을 쓰게된다. 그럴때는 처음부터 천천히 하나하나씩 따지다 보면 풀릴 것이니 너무 힘들어하지말고 겸손한 마음으로 천천히 풀어보려고 노력하자.