BOJ_1012 : 유기농 배추

👉 문제링크

1012번: 유기농 배추

---

---

🔸 문제 분석 🔸

• 지렁이가 퍼지는 범위는 배추가 가로세로로 붙어있는 범위를 뜻한다.
• 붙어있는 배추 그룹이 몇 개인지 출력한다.

🔸 코드 🔸

import sys
from collections import deque

dxy = [[0,-1],[-1,0],[0,1],[1,0]]

for _ in range(int(sys.stdin.readline())):
    m, n ,k = map(int, sys.stdin.readline().rstrip().split())

    field = [[0] * m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        field[y][x] = 1

    answer = 0
    visit = [[False] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            que = deque()
            if field[i][j] == 1 and visit[i][j] == False:
                que.append([i,j])
                field[i][j] = 0
                while len(que) > 0:
                    x, y = que.popleft()
                    visit[x][y] = True
                    for k in range(4):
                        dx = x + dxy[k][0]
                        dy = y + dxy[k][1]
                        
                        if dx < 0 or dx >= n or dy < 0 or dy >= m:
                            continue
                        
                        if field[dx][dy] == 1 and visit[dx][dy] == False:
                            field[dx][dy] = 0
                            que.append([dx,dy])
                answer += 1
    print(answer)

🔸 코드 해석 🔸

• BFS를 통해서 같은 그룹의 배추를 찾고, 그룹의 수를 출력한다.
  • m, n, k를 입력받고 n,m 으로 전체 밭을 조사해서 1을 찾는다.
  • 1을 찾은 인덱스부터 BFS를 시작한다.
    • 해당 좌표에서 좌 상 우 하 인덱스를 확인해 리스트 범위 내인지, 값은 1이고 방문한적 없는지 확인한다.
    • 범위내이며 값이 1이고 방문한적 없으면, 값을 0으로 만들고 큐에 해당 좌표를 넣는다.
    • 큐가 빌때까지 반복한다.
  • 큐의 반복이 끝나 BFS가 종료되면 그룹의 수를 1 더한다.

---

🔸 end 🔸

• 문제를 보고 지렁이의 움직임을 잘못 이해해 브루트포스로 착각해서 시간이 오래걸렸다.
  • 문제 입력이 n, m, k 가 아니라 m, n, k 순 입력인 것도 좀 헷깔리게 만들었다.
• BFS를 구현하는건 어렵지 않았는데 시간 초과가 나왔다.
  • 큐를 리스트에서 데크로 교체했다. 그래도 시간초과가 나왔다.
  • 큐에서 나온 좌표의 좌상우하 인덱스를 확인할때, 범위를 벗어나면 바로 continue를 해주었다. 통과했다.