글 읽기 - 안녕하세요 1987 알파벳 DFS관련 질문 요청드립니다!

dlswotmd 2년 전 0

다음 코드처럼 중복 처리를 위한 배열과 방문 처리를 위한 배열을 선언 후 dfs를 활용하여 문제 해결을 해보고자 했습니다! 문제에서 제공되는 샘플 케이스와 질문 게시판에 있는 몇가지 예제에서는 통과가 정상적으로 이루어지지만 이상하게 제출을 할때에는 2%에서 계속 막히고 있습니다. 혹시 제 코드에서 어떤 부분이 잘못 되었는지 여쭤보고 싶습니다!

import sys
sys.setrecursionlimit(10 ** 6)

# 가로 세로 입력
r, c  = map(int, sys.stdin.readline().split())

arr = []

# 배열에 입력데이터 추가
for _ in range(r):
    arr.append(list(sys.stdin.readline().rstrip()))

# 탐색을 위한 이동 방향 지정
moveX = [1, -1, 0, 0]
moveY = [0 , 0 , 1, -1]

# 방문처리를 위한 배열 선언
visited = [[False] * c for _ in range(r)]

# 중복 체크를 위한 배열 선언
dupliCheck = []

# dfs
def dfs(x, y):
    # 방문처리
    visited[y][x] = True    
    dupliCheck.append(arr[y][x])
    # 4방향 탐색 시작
    for i in range(4):        
        nx = x + moveX[i]
        ny = y + moveY[i]
        
        # 배열의 크기를 벗어나지 않는 경우에 다음 재귀 수행
        if 0 <= nx < c and 0 <= ny < r:     
            # 방문하지 않거나, 중복체크 되지 않은 곳에 대해 재귀 수행      
            if visited[ny][nx] == False and arr[ny][nx] not in dupliCheck:  
                # 중복 체크 배열에 값 추가                         
                dfs(nx, ny)            

# 결과 변수 선언
result = 0

# 배열 크기만큼 반복
for i in range(r):
    for j in range(c):
        # 방문하지 않은 위치에 한해서 dfs수행
        if visited[i][j] == False:
            dfs(j, i)            
            # 재귀 수행 후 배열의 길이를 결과변수와 비교,
            if result < len(dupliCheck):
                result = len(dupliCheck) # =>  결과변수를 변경 시킨다 0 => n
        # 중복 체크를 위한 배열을 다시 비워준다.
        dupliCheck = []

# 결과 변수 출력                
print(result)

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

문제

문제

출처

ICPC

안녕하세요 1987 알파벳 DFS관련 질문 요청드립니다!

dlswotmd 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말