[백준1012] 유기농 배추

https://www.acmicpc.net/problem/1012

 

문제 해결 방법

 

배추가 심긴 위치를 순회한다. 방문여부를 알 수 있는 visited 배열이 필요하다. 

좌표를 순회할때 1을 만나고, 방문한 적이 없으면 bfs함수를 실행한다. 

이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다. 이때 지렁이의 개수를 +1 한다 

bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 심겨진배추가 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 값이 0이 아니고 방문한 적이 없으면 현재자리의 방문체크를 해준다.  

 

그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다. 

 

코드 구현

정답 코드 

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

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

answer=[]
def bfs(y, x):
        queue = deque()
        visited[y][x] = True
        queue.append([y, x])

        while queue:
            ny, nx = queue.popleft()
            for ii in range(4):
                yy= ny+dy[ii]
                xx= nx+dx[ii]

                if 0<=yy<n and 0<=xx<m and mapp[yy][xx]==1 and  visited[yy][xx] == False:
                    visited[yy][xx] = True
                    queue.append([yy, xx])

t = int(input())
for j in range(t):
    m, n, k = map(int, input().split())
    mapp = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    cnt = 0
    for i in range(k):
        wm, wn = map(int, input().split())
        mapp[wn][wm] = 1
    
    for ix in range(n):
        for jx in range(m):
            if mapp[ix][jx]==1 and visited[ix][jx] == False:
                    cnt+=1
                    bfs(ix, jx)
    answer.append(cnt)

for i in answer:
  print(i)

 

시간/공간 복잡도

따로 생각하지 않았다. 

 

최적화 및 개선

• 따로 하지않음

 

어려웠던 점

• BFS는 큐에 넣기 전에 방문처리를 해야 중복 방문처리를 하지 않게 된다는 것을 알게됐다.