1012 유기농 배추

💡문제 분석 요약

• 이 문제와 거의 유사했다. 그리고 저 문제에다가 이차원 배열을 탐색하는 nx, ny 요소만 추가하면 됐다. 이 부분은 여기 문제와 유사했다. 저 두 문제의 방법을 합치면 될 것이다 !
• 결국, 지렁이가 몇마리냐 구하는 것은 DFS/BFS가 몇번 실행되느냐를 구하면 되는 것과 같은 맥락이었다. DFS가 아직은 더 편해서 DFS로 접근해보았다. 결국 모든 노드를 방문하는 맥락에서는 두 방법 모두 사용 가능하다.

💡알고리즘 설계

• 인접행렬, 인접리스트 2가지 방법으로 풀 수 있지만 인접행렬로 풀어보았다. 

💡코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(5000)

# 순서대로 상, 하, 좌, 우로 이동하는 것을 의미
dx = [0, 0, 1, -1] # x축 방향 이동
dy = [1, -1, 0, 0] # y축 방향 이동

earthworm = 0

def DFS(x, y):
    # 오류가 나는 상황을 정리한 것. 위, 아래로 움직이다가 x, y의 범위 밖으로 나가는 경우를 의미함.
    if x < 0 or x >= width or y < 0 or y >= height:
        return False

    if graph[x][y] == 1:
        graph[x][y] = 0
        for i in range(4): # 상하좌우 4개의 방향을 체크함
            nx = x + dx[i] # 기존의 좌표에 상하좌우를 더해줌
            ny = y + dy[i]
            DFS(nx, ny) # 더해준 상하좌우로 다시 탐색
        return True # 모든 탐색이 완료됨
    return False # 탐색이 끝나긴 했는데 0을 만나서 끝남. 즉 1로 둘러싼 경계 밖을 간 것.

for _ in range(int(input())):
    width, height, cabbages = map(int, input().split()) # 배추밭 가로, 배추밭 세로, 배추개수
    graph = [[0] * (height) for _ in range(width)]  # 배추밭 초기화
    visited = [[0] * (height) for _ in range(width)]
    earthworm = 0  # 지렁이

    # 배추가 심어져 있는 곳 초기화
    for _ in range(cabbages):
        u, v = map(int, input().split())
        graph[u][v] = 1
    # 초기화 끝
    for x in range(width):
        for y in range(height):
            if graph[x][y] == 1:
                DFS(x, y)
                earthworm += 1
    print(earthworm)

💡시간복잡도

• 모든 노드를 방문하므로 O(N^2)이 소요될 것이다. (정확히는 O(N*M) )

💡 틀린 이유

• 위에서 언급한 두개의 문제를 합치는 과정 & 그래프 초기화 하는 것에서 약간 애를 먹었다.
• visited를 선언할지 말지도 고민이었는데, 어차피 graph가 1인 곳만 방문하고, 방문한 곳은 0으로 바꿔주기 때문에 상관이 없을 것으로 보였다.
• 어이없게 하나 틀렸던 것도 있는데, 그동안 항상 노드의 시작을 1~N으로 해서 그래프 초기화 범위도 range( 1~N+1 ) 라고 했는데, 이번에도 그래프 초기화를 이렇게 했다가 입력값에 0,0이 있는 것을 보고 급히 0~N으로 range를 수정하였다. 문제를 잘 읽고 풀자 !

💡 틀린 부분 수정 or 다른 풀이

import sys
input = sys.stdin.readline

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

def BFS(x, y):
    queue = [(x,y)]
    graph[x][y] = 0

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

for i in range(int(input())):
    M,N,K = map(int, input().split())
    graph = [[0]*(N) for _ in range(M)]
    count = 0
    for j in range(K):
        x,y = map(int, input().split())
        graph[x][y] = 1
        
    for x in range(M):
        for y in range(N):
            if graph[x][y] == 1:
                BFS(x, y)
                count += 1
    print(count)

💡 느낀점 or 기억할정보

• BFS로도 풀어보자.
• 범위를 생각없이 1~N+1로 잡았던 것을 반성하며 문제를 잘 읽고 풀자 !