[파이썬/Python/백준알고리즘]1012. 유기농배추

SooYeon Yeon·2022년 8월 17일
0

파이썬/알고리즘

목록 보기
32/35

풀이

import sys

def makeField(m,n):
    field = [[0]*m for i in range(n)]
    return field

def dfs(field,i,j):
    stack=[]
    stack.append([i,j])
    while stack:
        # 상하좌우 확인
        tmp = stack.pop()
        field[tmp[0]][tmp[1]] = -1

        # 상
        if tmp[0]!=0:
            if field[tmp[0]-1][tmp[1]] == 1 :
                field[tmp[0]-1][tmp[1]] = -1
                #dfs(field, tmp[0]-1, tmp[1])
                stack.append([tmp[0]-1,tmp[1]])

            elif field[tmp[0]-1][tmp[1]] == 0 or field[tmp[0]-1][tmp[1]] == -1:
                pass
            elif not stack:
                break

        # 하
        if tmp[0]!=len(field)-1:
            if field[tmp[0]+1][tmp[1]] == 1 :
                field[tmp[0]+1][tmp[1]] = -1
                #dfs(field, tmp[0]+1, tmp[1])
                stack.append([tmp[0]+1, tmp[1]])
            elif field[tmp[0]+1][tmp[1]] == 0 or field[tmp[0]+1][tmp[1]] == -1:
                pass
            elif not stack:
                break

        # 좌
        if tmp[1]!=0:
            if field[tmp[0]][tmp[1]-1] == 1 :
                field[tmp[0]][tmp[1]-1] = -1
                #dfs(field, tmp[0], tmp[1]-1)
                stack.append([tmp[0], tmp[1]-1])
            elif field[tmp[0]][tmp[1]-1] == 0 or field[tmp[0]][tmp[1]-1] == -1:
                pass
            elif not stack:
                break

        # 우
        if tmp[1]!=len(field[0])-1:
            if field[tmp[0]][tmp[1]+1] == 1 :
                field[tmp[0]][tmp[1]+1] = -1
                #dfs(field,tmp[0],tmp[1]+1)
                stack.append([tmp[0], tmp[1]+1])
            elif field[tmp[0]][tmp[1]+1] == 0 or field[tmp[0]][tmp[1]+1] == -1:
                pass
            elif not stack:
                break

T = int(sys.stdin.readline())

for t in range(T):
    tmp = sys.stdin.readline().split()
    M = int(tmp[0])
    N = int(tmp[1])
    K = int(tmp[2])

    field = makeField(M,N)
    for k in range(K):
        tt = sys.stdin.readline().split()
        field[int(tt[1])][int(tt[0])] = 1
    cnt = 0
    # 탐색 시작
    for i in range(N):
        for j in range(M):
            if field[i][j] == 1 :
                cnt += 1
                dfs(field,i,j)
            else:
                field[i][j] = -1
    print(cnt)
  1. 먼저 field에 0으로 초기화 하고, 받은 값에 대해서 배추 위치를 1로 한다.
  2. 처음부터 탐색을 시작하면서 배추가 있는 위치라면 먼저 cnt를 해주고, dfs를 실행한다.
  3. dfs함수에서는 stack에 i,j 위치를 넣고 보는데, 일단 방문한 i, j는 -1로 바꾸어준다.
  4. stack이 존재할때까지 돌리며 상하좌우에 대한 내용을 보고, 만약 1(배추)라면 -1로 바꾸어주고, stack에 해당 인덱스(상하좌우로 간 값)를 추가해준다.
  5. 만약, 1이 아닌 0이나 -1이라면 나머지를 이어 진행한다.

dfs 함수 안에서 재귀함수로 실행해서 런타임 에러가 계속 떴었다 (주석처리한 내용)

해당 부분을 수정했더니 됐다.

0개의 댓글