[백준] 1012. 유기농 배추 (실버2, Python)

 

풀이

* 각 시도 모두 메인 부분은 동일하고 'findEarthworm()' 함수 부분만 변경함.

 

1차 시도

1이 연결되어 있는 노드 끝까지 탐색 후, 옆 노드로 이동해서 끝까지 탐색함으로 깊이우선탐색알고리즘이라고 판단

그래서 스택과 재귀를 활용하여 구현해야 겠다고 생각해서 아래와 같이 구현

 

현재 노드 기준으로 연결된 노드가 1이고 아직 방문하지 않았다면 해당 함수 재귀로 호출

함수 호출되면 스택에 현재 노드 저장 후, while에서 하나 빼서 사용

def findEarthworm(startY, startX):
    checkArr[startY][startX] = True
    nearNode.append([startY, startX])
    
    # 앞뒤위아래
    moveXArr = [1, -1, 0, 0]
    moveYArr = [0, 0, -1, 1]
    
    while len(nearNode) > 0:
        nowNode = nearNode.pop()
        for i in range(4):
            moveX = nowNode[1] + moveXArr[i]
            moveY = nowNode[0] + moveYArr[i]
            
            if moveX < 0 or moveY < 0:
                continue
            if moveX >= m or moveY >= n:
                continue
            
            if targetArr[moveY][moveX] == 1 and not checkArr[moveY][moveX]:
                findEarthworm(moveY, moveX)

 

그래서 나온 결과...! 뭐가 문제인지 몰라서 같은 코드를 3번이나 제출함....ㅎㅎ

구글링이랑 백준 런터임 에러 정리 페이지 방문으로 해결함..!

그 중 내 코드의 에러, RecursionError 였다...! 백준에서 재귀 깊이가 1,000으로 되어 있는데 나는 그걸 넘었나보다....

 

그래서 일단 임시방편으로 아래와 같은 코드를 상단에 위치했다. 결과는 성공적...!

import sys;
sys.setrecursionlimit(10**5)

 

 

2차 시도

런타임 에러때문에 함수를 너무 많이 호출하는 것을 깨달았다. 그래서 불필요한 코드를 확인해보았고, 보다보니 while문과 stack의 활용이유가 없었다... 바보...ㅎ

그냥 스택에 넣자마자 while에서 바로 빼니 의미가 없었다...

그래서 제거하고 다시 제출!

def findEarthworm(startY, startX):
    checkArr[startY][startX] = True
    
    # 앞뒤위아래
    moveXArr = [1, -1, 0, 0]
    moveYArr = [0, 0, -1, 1]
    
    for i in range(4):
        moveX = startX + moveXArr[i]
        moveY = startY + moveYArr[i]
        
        if moveX < 0 or moveY < 0:
            continue
        if moveX >= m or moveY >= n:
            continue
        
        if targetArr[moveY][moveX] == 1 and not checkArr[moveY][moveX]:
            findEarthworm(moveY, moveX)

그 덕분에 시간과 메모리 사용량이 줄었다..! 

 

하지만 여전히 sys.setrecursionlimit 없으면 런타임 에러 발생한다. 그래서 다른 사람의 제출 코드를 확인해보니 큐를 사용한것을 알 수 있었다...

 

깊이우선인줄 알았으나... 너비 우선이었다는....ㅎㅎ

그 부분은 다음에 다시 풀어보도록 하겠다! (*아래 큐 사용한 풀이 있음)

 

 

최종 코드

import sys;
sys.setrecursionlimit(10**5)

def findEarthworm(startY, startX):
    checkArr[startY][startX] = True
    
    # 앞뒤위아래
    moveXArr = [1, -1, 0, 0]
    moveYArr = [0, 0, -1, 1]
    
    for i in range(4):
        moveX = startX + moveXArr[i]
        moveY = startY + moveYArr[i]
        
        if moveX < 0 or moveY < 0:
            continue
        if moveX >= m or moveY >= n:
            continue
        
        if targetArr[moveY][moveX] == 1 and not checkArr[moveY][moveX]:
            findEarthworm(moveY, moveX)
            

tc = int(input())

for i in range(tc):
    # nearNode = []
    result = 0
    m, n, k = map(int, input().split())
    targetArr = [[0]*m for _ in range(n)] # 양배추 위치 저장
    checkArr = [[False]*m for _ in range(n)] # 방문 기록
    
    # 값 세팅
    minX, minY = 51, 51
    for c in range(k):
        x, y = map(int, input().split())
        targetArr[y][x] = 1
        
    for y in range(n):
        for x in range(m):
            if targetArr[y][x] == 1 and not checkArr[y][x]:
                findEarthworm(y, x)
                result+=1
    print(result)

 

그래서 재귀 깊이를 제한하지 않고 구현해보려고 큐와 스택을 활용해봤다.

 

Queue 활용

def useQueue(startY, startX):
    nearNode = queue.Queue()
    checkArr[startY][startX] = True
    nearNode.put([startY, startX])
    
    # 앞뒤위아래
    moveXArr = [1, -1, 0, 0]
    moveYArr = [0, 0, -1, 1]
    
    while nearNode.qsize() > 0:
        node = nearNode.get()
        
        for i in range(4):
            moveX = node[1] + moveXArr[i]
            moveY = node[0] + moveYArr[i]
            
            if moveX < 0 or moveY < 0:
                continue
            if moveX >= m or moveY >= n:
                continue
            
            if targetArr[moveY][moveX] == 1 and not checkArr[moveY][moveX]:
                checkArr[moveY][moveX] = True
                nearNode.put([moveY, moveX])

 

Stack 활용

def findEarthworm_ver2(startY, startX):
    nearNode = []
    checkArr[startY][startX] = True
    nearNode.append([startY, startX])
    
    # 앞뒤위아래
    moveXArr = [1, -1, 0, 0]
    moveYArr = [0, 0, -1, 1]
    
    while len(nearNode) > 0:
        node = nearNode.pop()
        
        for i in range(4):
            moveX = node[1] + moveXArr[i]
            moveY = node[0] + moveYArr[i]
            
            if moveX < 0 or moveY < 0:
                continue
            if moveX >= m or moveY >= n:
                continue
            
            if targetArr[moveY][moveX] == 1 and not checkArr[moveY][moveX]:
                checkArr[moveY][moveX] = True
                nearNode.append([moveY, moveX])

결과

해당 문제는 DFS, BFS 상관없이, 둘다 가능했다.

문제를 다시 읽어보니 최단 거리, 미로탐색이 아니기에 1로 이어진 덩어리 개수만 구하면 되기 때문에 무엇이든 상관없다...!

 

 

백준 문제

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

 

GitHub

https://github.com/ujin302/CodingTest_2023/blob/main/Code/BackJun/silver/s2/s2_1012.py

CodingTest_2023/Code/BackJun/silver/s2/s2_1012.py at main · ujin302/CodingTest_2023