백준 너비 우선 탐색 문제풀이 입니다.

문제

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

[나의 풀이1]

T = int(input())

farms = []
visited = []

for i in range(T):
    M, N, K = map(int, input().split())

    farms.append([[0] * N for x in range(M)])
    visited.append([[False] * N for x in range(M)])

    for j in range(K):
        x, y = map(int, input().split())

        farms[i][x][y] = 1

from collections import deque

# 상우하좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for t in range(len(farms)):
    length = len(farms[t])
    width = len(farms[t][0])

    print("가로 : ", length,"세로 : ",width)

    ans = 0
    add = 0
    queue = deque([[0, 0]])
    visited[t][0][0] = True
    last_v = [0,0]
    ans_list = []

    if farms[t][0][0] == 1:
        ans_list.append([0,0])

    while queue:

        print("queue : ",queue) 
        v = queue.popleft()
        print("현재 좌표 : ", v[0], v[1])
        
        for i in range(4):
            if v[0] + dx[i] >= 0 and v[0] + dx[i] < length and v[1] + dy[i] >= 0 and v[1] + dy[i] < width :
                if not visited[t][v[0] + dx[i]][v[1] + dy[i]]:
                    if farms[t][v[0] + dx[i]][v[1] + dy[i]] == 1:
                        queue.appendleft([v[0] + dx[i], v[1] + dy[i]])
                        ans_list.append([v[0] + dx[i], v[1] + dy[i]])
                    else:
                        queue.append([v[0] + dx[i], v[1] + dy[i]])
                    visited[t][v[0] + dx[i]][v[1] + dy[i]] = True

        last_v = v

    last_x0 = ans_list[0][0]
    last_x1 = ans_list[0][1]

    if len(ans_list) == 1:
        ans = 1
        print(ans)
        break

    ans_list = sorted(ans_list)

    for idx,x in enumerate(ans_list):

        if idx == len(ans_list)-1:
            break
        if (abs(ans_list[idx][0] - ans_list[idx+1][0]) == 1 and ans_list[idx][1] - ans_list[idx+1][1] == 0) or (ans_list[idx][0] - ans_list[idx+1][0] == 0 and abs(ans_list[idx][1] - ans_list[idx+1][1]) == 1) :
            continue
        print()
        print("ans 추가 : ", idx,x)
        ans += 1

    print(ans_list)
    print(ans)

너비 우선 탐색 작동 방식은 이해하고 있지만 풀이 접근을 잘못하여 해결하지 못하였습니다. 위 코드는 너비 우선 탐색 방식으로 1(양배추)인 좌표를 우선으로 조사하여 ans_list(양배추 좌표)를 appendleft하고 0(비어있는) 좌표를 오른쪽에 append한 뒤 ans_list를 순차적으로 돌며 좌표차이가 ±1인 좌표를 묶어 양배추 더미의 갯수를 조사하려고 했습니다. 하지만 이러한 방식은 예를 들어

ans_list = [[0, 0], [1, 0], [1, 1], [2, 4], [3, 4], [4, 2], [4, 3], [4, 5], [7, 4], [7, 5], [7, 6], [8, 4], [8, 5], [8, 6], [9, 4], [9, 5], [9, 6]]

일 때, [7,6] 과 [8,6]은 같은 더미임에도 불구하고 [0, 0], [1, 0], [1, 1] / [2, 4], [3, 4] / [4, 2], [4, 3] / [4, 5] / [7, 4], [7, 5], [7, 6] / [8, 4], [8, 5], [8, 6] ... 씩 끊어 세기 때문에 정답보다 더 많은 더미로 출력되었습니다. 해결하기 어려워 다른 풀이를 참고하였습니다.🧸🧸🧸

[나의 풀이2]

T = int(input())

def bfs(farm,x,y):

    from collections import deque

    queue = deque([[x,y]])
    visited[x][y] = True
    
    while queue:

        v = queue.popleft()
        
        x = v[0]
        y = v[1]

        farm[x][y] = 0
            
        for k in range(4):
            Newx = x + dx[k]
            Newy = y + dy[k]

            if Newx >=0 and Newx < M and Newy >= 0 and Newy < N:
                if not visited[Newx][Newy]:
                    if farm[Newx][Newy] == 1:
                        queue.append([Newx,Newy])
                        visited[Newx][Newy] = True

        # print(queue)

# 상우하좌
dx = [-1,0,1,0]
dy = [0,1,0,-1]      

for _ in range(T):
    M, N, K = map(int,input().split())

    farm = [[0]*N for m in range(M)]
    visited = [[False]*N for m in range(M)]

    for k in range(K):

        i,j = map(int,input().split())
        farm[i][j] = 1

    ans = 0
    for x in range(M):
        for y in range(N):

            if farm[x][y] == 1:
                ans += 1
                bfs(farm,x,y)
    
    print(ans)

[다른사람의 풀이]

from collections import deque

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

t = int(input())

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >=n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
    return

for i in range(t):
    cnt = 0
    n, m, k = map(int,input().split())
    graph = [[0]*m for _ in range(n)]

    for j in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1

    for a in range(n):
        for b in range(m):
            if graph[a][b] == 1:
                bfs(graph, a, b)
                cnt += 1
    print(cnt)

위 다른 사람의 풀이와 같이 전체 농장을 돌며 여러 양배추 더미 중 한 부분을 탐지하면 이와 연결된 1을 모두 파악하여 0으로 바꾸며 한 더미씩 세는 방식이었습니다. 양배추인 좌표(값이 1인 좌표)를 우선으로 탐색하기 위해 bfs 구조를 사용한 것을 깨달을 수 있었습니다.🦝🦝🦝

감사합니다.