[DFS] 1012번 유기농배추 - 실버2

[heerucan]

https://www.acmicpc.net/user/jwyandkrh

문제 정리

• 0은 배추X, 1은 배추O
• 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사
• 결국 연결요소 구하는 문제니까 dfs로 풀자! : dfs는 스택을 사용하는 것
• m : 배추밭의 가로
• n : 세로
• k : 배추 개수

import sys
sys.setrecursionlimit(10**7)

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    else:
        # 1인 아이들에 한해서 탐색시 방문처리로 0으로 바꾸고, 상하좌우 탐색
        # 연결요소 개수 카운팅! 필요! 
        if graph[x][y] == 1:
            graph[x][y] = 0
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1)
            dfs(x, y+1)
            return True
    return False

# 테스트케이스 입력받아서 돌기
for _ in range(int(input())):
    graph = []
    m, n, k = map(int, input().split())

    graph = [[0]*m for _ in range(n)]

    # 좌표 받아서 1로 바꾸기
    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    worm = 0
    for i in range(0, n):
        for j in range(0, m):
            if dfs(i, j) == True:
                worm += 1

    print(worm)

문풀 정리

• dfs라고 생각한 이유는 우선 연결요소 문제랑 비슷하다고 생각했다. 연결요소 즉, 그래프 내 노드덩어리 개수를 구하는 문제였다.
• 그리고 기존 문제랑 다르게 좌표를 줘서 좌표에 해당하는 놈들만 1로 값을 바꾸는 게 추가된 정도였다.

헷갈린 점

• 내가 헷갈린 부분은 그래프에서 가로, 세로 입력값을 줄 때 m, n으로 해주면 당연히 그래프도 graph[x][y]라고 생각했는데 그 경우에는
  [[0, 0, 0, 0, 1], [0, 0, 0, 0, 0], [1, 1, 1, 1, 1]] 이런 식으로 그래프가 그려지기 때문에 앞에 오는 값이 y좌표여야 한다. 그래서 graph[y][x]여야 했고, 따라서 m이 가로지만 y에 관한 값이고, n은 세로지만 x에 관한 값이니 관련된 부분을 다 고쳐줘야 한다.

이 문제에는 슬푼 전설이 있어..

답지 보고 풀었던 문제였는데 이번에 답지 안보고 풀어서 맞췄다. 접근법이랑 어떻게 풀어야 하는지도 혼자 생각해냈다. 다만 이제 dfs 풀이법을 다 못외워서 다른 dfs 문제 푼 거 참고한 거가 아쉬울 뿐..