백준_1012 (유기농 배추_DFS 핵심문제_Recursion error 해결법 (중요))

---

미리 작성해두는 내용 (중요) Recursion Error 해결법

• DFS 를 재귀로 풀다보면 런타임 에러가 뜬다
  - 이유는 Recursion Error : Recursion이 너무 깊어서 생기는 에러임
  - 백준에선 알려주는데 프로그래머스에선 런타임 에러만 뜸
  
• 해결 방법은 sys.set recursion limit(큰수) 을 사용해서 엄청 큰 수로 강제로 바꿔버리는 것!!
  - sys. 설정한다 recursion의 리밋을 ( )으로
  

import sys
sys.setrecursionlimit(10**5)             # (중요) Recursion 늘리기!!!

---

• 링크 : https://www.acmicpc.net/problem/1012

---

내가 처음에 접근할 때 생각한 것

체크할 사항

• 상하좌우 네 방향으로만 인접한 것으로 취급

• 1 = 배추 // 0 = 배추x

• 배추 한 그룹 당 지렁이 1마리만 있으면 된다

  • DFS였네
  • 일단 1차적으로 while로 풀스캔하는데 그 안에서 for DFS() 1회 수행 시 cnt += 1
  • 동빈나였나 어디 문제랑 비슷한 유형임 결국

• Input에서 N x M 행렬이다 (N x N 아님)

• K개의 배추가 있고, (x, y)로 입력받는다 => 좌표로 그래프 배열 만들어야한다(이웃 이런거 필요 X)

  • 만들고 나서 위에 써둔거 수행하면 될듯

---

• 1차적으로 푼 내용 :
  - 일단 그래프 변환 시 x, y가 아니라 y, x인데 잘못했다
  - 그리고 일단 매번 입력하기 귀찮아서 값을 박아버리고 시작했다.
  

''' 내가 푼 1차 접근 - x,y 를 거꾸로 잘못했다 '''
def dfs(x, y, graph, m, n):
    graph[x][y] = 0                      # DFS니까 다시는 올 수 없게 체크
    #     상 하 좌 우  (근데 내가 꺼꾸로함 원래 (y,x)인데 )
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    print('x, y = ', x, ' ', y)
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if ny < 0 or m <= ny or nx < 0 or n <= nx:
            continue
        
        print('nx, ny = ', nx, ' ', ny)
        if graph[nx][ny] == 1:
            dfs(nx, ny, graph, m, n)
    print('------------')

for _ in range(int(input())):            # 테스트케이스 개수 t (밑에 10 10 1 은 새로운 테스트케이스임)
    answer = 0
    '''
    m, n, k = map(int, input().split())  # 가로 m   세로 n   배추 개수 k
    
    arr = []
    
    # 그래프 생성
    graph = [[0 for _ in range(n)] for _ in range(m)]
    for _ in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1
        arr.append([x, y])               # 브루트폴스 안하고 필요한 위치만 하기 위함
    '''
    # 입력 귀찮아서 값을 박아둠
    m, n, k = 10, 8, 17
    graph = [[1, 0, 0, 0, 0, 0, 0, 0], 
             [1, 1, 0, 0, 0, 0, 0, 0], 
             [0, 0, 0, 0, 1, 0, 0, 0], 
             [0, 0, 0, 0, 1, 0, 0, 0], 
             [0, 0, 1, 1, 0, 1, 0, 0], 
             [0, 0, 0, 0, 0, 0, 0, 0], 
             [0, 0, 0, 0, 0, 0, 0, 0], 
             [0, 0, 0, 0, 1, 1, 1, 0], 
             [0, 0, 0, 0, 1, 1, 1, 0], 
             [0, 0, 0, 0, 1, 1, 1, 0]]
    arr = [[0, 0], [1, 0], [1, 1], [4, 2], [4, 3], [4, 5], [2, 4], [3, 4], [7, 4], [8, 4], [9, 4], [7, 5], [8, 5], [9, 5], [7, 6], [8, 6], [9, 6]]

    for x, y in arr:                    # 브루트폴스 안하고 필요한 위치만 하기 위함
        if graph[x][y] == 1:
            dfs(x, y, graph, m, n)
            answer += 1                  # DFS "순회"가 1회 끝날 때마다 +1
    print(answer)
        

• 2차적으로 푼 내용 :
  - x, y 잘못한걸 y, x로 고치니까 테스트 케이스는 성공했다. (arr도 뒤집어줬다!!!)
  - 다만, 백준에서 제출 시 "Runtime error"가 떴다.
  - 앞서 작성했던 recursion error인데, sys.set recursion limit()을 큰 수로 설정해주자
  

''' 내가 푼 -> xy 다시! 뒤집어 -> 귀찮아서 값 박아둔 솔루션 (답은 맞는데 sys안써서 런타임 에러가 떴음) '''
def dfs(y, x, graph, m, n):
    graph[y][x] = 0                      # DFS니까 다시는 올 수 없게 체크
    #     상 하 좌 우 
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if ny < 0 or m <= ny or nx < 0 or n <= nx:
            continue
       
        if graph[ny][nx] == 1:
            dfs(ny, nx, graph, m, n)

for _ in range(int(input())):            # 테스트케이스 개수 t (밑에 10 10 1 은 새로운 테스트케이스임)
    answer = 0
    '''
    m, n, k = map(int, input().split())  # 가로 m   세로 n   배추 개수 k
    
    arr = []
    
    # 그래프 생성
    graph = [[0 for _ in range(n)] for _ in range(m)]
    for _ in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1
        arr.append([x, y])               # 브루트폴스 안하고 필요한 위치만 하기 위함
    '''
    m, n, k = 10, 8, 17
    graph = [[1, 0, 0, 0, 0, 0, 0, 0], 
             [1, 1, 0, 0, 0, 0, 0, 0], 
             [0, 0, 0, 0, 1, 0, 0, 0], 
             [0, 0, 0, 0, 1, 0, 0, 0], 
             [0, 0, 1, 1, 0, 1, 0, 0], 
             [0, 0, 0, 0, 0, 0, 0, 0], 
             [0, 0, 0, 0, 0, 0, 0, 0], 
             [0, 0, 0, 0, 1, 1, 1, 0], 
             [0, 0, 0, 0, 1, 1, 1, 0], 
             [0, 0, 0, 0, 1, 1, 1, 0]]
    arr = [[0, 0], [1, 0], [1, 1], [4, 2], [4, 3], [4, 5], [2, 4], [3, 4], [7, 4], [8, 4], [9, 4], [7, 5], [8, 5], [9, 5], [7, 6], [8, 6], [9, 6]]
    
    for i in range(k):
        arr[i].reverse()                # 얘도 각각 뒤집어줘야한다! x, y를!
    
    for x, y in arr:                    # 브루트폴스 안하고 필요한 위치만 하기 위함
        if graph[y][x] == 1:
            dfs(y, x, graph, m, n)
            answer += 1                 # (중요) DFS "순회"가 1회 끝날 때마다 +1
    print(answer)        

• 최종 정답

''' 내가 푼 -> xy 다시! 뒤집어 -> 제출용 '''
import sys
sys.setrecursionlimit(10**5)             # (중요) Recursion 늘리기!!!

def dfs(y, x, graph, m, n):
    graph[y][x] = 0                      # DFS니까 다시는 올 수 없게 체크
    #     상 하 좌 우 
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if ny < 0 or m <= ny or nx < 0 or n <= nx:
            continue
       
        if graph[ny][nx] == 1:
            dfs(ny, nx, graph, m, n)

for _ in range(int(input())):            # 테스트케이스 개수 t (밑에 10 10 1 은 새로운 테스트케이스임)
    answer = 0
    
    m, n, k = map(int, input().split())  # 가로 m   세로 n   배추 개수 k
    
    arr = []
    
    # 그래프 생성
    graph = [[0 for _ in range(n)] for _ in range(m)]
    for _ in range(k):
        x, y = map(int, input().split())
        graph[x][y] = 1
        arr.append([x, y])              # 브루트폴스 안하고 필요한 위치만 하기 위함
        
    for i in range(k):
        arr[i].reverse()                # 얘도 각각 뒤집어줘야한다! x, y를!
    
    for x, y in arr:                    # 브루트폴스 안하고 필요한 위치만 하기 위함
        if graph[y][x] == 1:
            dfs(y, x, graph, m, n)
            answer += 1                 # DFS "순회"가 1회 끝날 때마다 +1
    print(answer)