글 읽기 - Python3, DFS 반례좀 부탁드립니다

dudqja8847 3년 전 1

자꾸 33%에서 틀렸다고 나오는데 반례좀 부탁드리겠습니다 고수님들

import pprint
import sys
sys.setrecursionlimit(10000)

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

T = int(input())

result = []
matrix = []
visited = []
jirungee = 0

def dfs(x, y):
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < M and ny < N:
            if visited[nx][ny] == 0 and matrix[nx][ny] == 1:
                dfs(nx, ny)

for _ in range(T):
    # 배추 밭의 가로 길이 M, 세로 길이 N, 배추가 심어져 있는 위치의 개수 K
    M, N, K = map(int, input().split(' '))

    matrix = [[0] * N for _ in range(M)]
    visited = [[0] * N for _ in range(M)]
    for _ in range(K):
        x, y = map(int, input().split(' '))
        matrix[x][y] = 1


    for a in range(M):
        for b in range(N):
            if matrix[a][b] == 1 and visited[a][b] == 0:
                dfs(a, b)
                jirungee += 1
    result.append(jirungee)
    jirungee = 0
    visited = []
    matrix = []

for e in result:
    print(e)

dldyddlwl 3년 전 1

아래 부분을 조심하세요

if 0 <= nx < M and ny < N:

// ny도 마찬가지로 ny >= 0

dudqja8847 3년 전 0

@dlduddlwl

감사합니다! 이쁘게 코드 써본다고 깜빡했네요. 덕분에 통과 했습니다! 😁

import pprint
import sys

sys.setrecursionlimit(10000)

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

T = int(input())

result = []
matrix = []
visited = []
jirungee = 0


def dfs(x, y):
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N:
            if visited[nx][ny] == 0 and matrix[nx][ny] == 1:
                dfs(nx, ny)


for _ in range(T):
    # 배추 밭의 가로 길이 M, 세로 길이 N, 배추가 심어져 있는 위치의 개수 K
    M, N, K = map(int, input().split(' '))

    matrix = [[0] * N for _ in range(M)]
    visited = [[0] * N for _ in range(M)]
    for _ in range(K):
        x, y = map(int, input().split(' '))
        matrix[x][y] = 1

    for a in range(M):
        for b in range(N):
            if matrix[a][b] == 1 and visited[a][b] == 0:
                dfs(a, b)
                jirungee += 1
    result.append(jirungee)
    jirungee = 0
    visited = []
    matrix = []

for e in result:
    print(e)

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

문제

문제

출처

ICPC

Python3, DFS 반례좀 부탁드립니다

dudqja8847 3년 전 1

dldyddlwl 3년 전 1

dudqja8847 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말