글 읽기 - [ Python 3 ] DFS 33%에서 틀렸다고 나옵니다.

bej2ny8 3년 전 0

좌표대로 1을 찍은, 그외에는 0을 찍은 field를 만든 뒤에 field가 1이라면 인접한 부분의 field를 찾아가면서 벌레의 개수를 찾는 DFS를 생각했는데 33%에서 계속 오답처리가 됩니다.

나름 완벽하게 짠 것 같은데 어느 부분이 틀렸는지 모르겠네요...

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y) :
    global stack
    if field[y][x] != 0 :
        field[y][x]=0
        for i in range(4) :
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<row and 0<=yy<col :
                if field[yy][xx]==1 :
                    stack.append([xx,yy])
        if stack :
            k=stack.pop()
            return dfs(k[0],k[1])

test_case=int(input())
for _ in range(test_case) :
    row,col,count=map(int,input().split())
    dot=[list(map(int,input().split())) for _ in range(count)]
    field=[[0 for _ in range(row)] for _ in range(col)]
    worm=0;stack=[]
    for i in range(count) :
        field[dot[i][1]][dot[i][0]]=1
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
    for i in range(row) :
        for j in range(col) :
            if field[j][i] == 1 :
                worm+=1
                dfs(i,j)
    print(worm)

dldyddlwl 3년 전 1

아래에 있습니다.

표시해둔 부분이 전체 if문인 != 0 조건에 가려져선 안되는 이유는,

만약에 stack에 같은 것이 중복해서 들어가졌다고 합시다. ( 스택에 방문조건 없이 바로 넣으므로 중복 발생 가능)

그러면, 먼저 빠져나오는 친구가 0으로 바뀌면서, 뒤에 있는 친구의 값도 0이 됩니다.

그런데 뒤에 나온 친구의 순서가 왔을 때, 기존의 조건(0이 아니다)으로는 스택에서 pop도 되지 못하므로, 문제가 생기게 됩니다.

import sys
sys.setrecursionlimit(10**6)

def dfs(x,y) :
    global stack
    if field[y][x] != 0 :
        field[y][x]=0
        for i in range(4) :
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<row and 0<=yy<col :
                if field[yy][xx]==1 :
                    stack.append([xx,yy])
        if stack :                             # 이 부분이 전체 if에 가려져선 안됩니다
            k=stack.pop()
            return dfs(k[0],k[1])

# 개선안


def dfs(x,y) :
    global stack
    if field[y][x] != 0 :
        field[y][x]=0
        for i in range(4) :
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<row and 0<=yy<col :
                if field[yy][xx]==1 :
                    stack.append([xx,yy])
    if stack :                             # 이 부분이 전체 if에 가려져선 안됩니다
        k=stack.pop()                        #  0이든 0이 아니든 스택에서 빠져나와야 합니다
        return dfs(k[0],k[1])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[ Python 3 ] DFS 33%에서 틀렸다고 나옵니다.

bej2ny8 3년 전 0

dldyddlwl 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말