백준 1012 python

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

고민

해당 문제의 핵심은 상하좌우로 연결된 요소 뭉치의 개수를 어떻게
구할 것인가이다.

모든 요소를 한번씩 방문해야하나?
방문했다면 현재 뭉치에 근접해있던 요소인지는 어떻게 판단할 수 있지?

그래서 해당 알고리즘의 분류를 살펴보니
그래프 이론, 그래프 탐색 이 두가지 키워드가 있네? 한번 찾아봐야지

그래프 구현 방식은 인접 리스트, 인접 행렬 두가지가 있는데, 인접 행렬로 구현하면 되겠네!

import sys
from collections import deque

# 우 하 좌 상 (시계방향)
moveX = [1, 0, -1, 0]
moveY = [0, -1, 0, 1]
cnt = 0

def bfs(x, y):
    Q = deque()
    Q.append((y, x))
    graph[y][x] = 0
    
    while Q:
        y, x = Q.popleft()
        
        for i in range(4):
            newY = y + moveY[i]
            newX = x + moveX[i]
            
            if(newY < 0 or newX < 0 or newY >= n or newX >= m):
                continue
            
            if(graph[newY][newX] == 1):
                Q.append((newY, newX))
                graph[newY][newX] = 0
    
    
T = int(input())

for _ in range(T):
    # m=가로, n=세로, k=심어져있는배추개수
    m, n, k = map(int, input().split())
    graph = [[0]*m for _ in range(n)]
    
    # 그래프 그리기
    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    # 인접 행렬 그래프이기 때문에 전체를 순환하면서 확인
    for y in range(n):
        for x in range(m):
            if(graph[y][x] == 1):
                bfs(x, y)
                cnt+=1
    print(cnt)
    cnt = 0

풀이

인접 리스트, 인접 행렬 중 인접 행렬 방식으로 구현 했다.
(문제 자체가 그렇게 풀라고 나온 것 같다.)

인접 행렬이기 때문에 모든 그래프를 순회할 수 밖에 없는 듯 하다.

순회하면서 상하좌우 배추 확인 및 존재한다면 큐에 담아주면서 이동한다.

이걸 계속 반복

bfs 함수의 일부는 다른 사람의 소스를 참고했는데

방문여부 배열 생성없이 현재 좌표 값을 0으로 바꿔주면

큐에 담기지않고 방문처리를 할 수 있어서 로직도 원하는대로 흘러가고

메모리도 아낄 수 있다! 좋은듯 하다.