[알고리즘] 백준 1987 - 알파벳

문제

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

1987번: 알파벳

 

풀이

얘도 예전에 이미 풀었던 문제인데.. 딱 봤을 때 간단한 dfs같은데 왜이리 정답율이 낮은건가 싶었다.

나도 dfs로 풀었고 방문한 알파벳을 set형태의 visited에 add해주는 식으로 관리했다. 파이썬3으로 하면 시간 초과가 나고 pypy로 해야 엄청 느릿느릿 채점돼서 통과한다.

 

 

코드

import sys
input=sys.stdin.readline

r,c = map(int,input().split())
table=[]
dx=[1,-1,0,0]
dy=[0,0,-1,1]
answer = 0
visited=set()

def dfs(x,y,cnt):
    global answer

    answer = max(answer,cnt)

    visited.add(table[x][y])
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        
        if 0<=nx<r and 0<=ny<c and table[nx][ny] not in visited:
            dfs(nx,ny,cnt+1)

    visited.remove(table[x][y])

for _ in range(r):
    tmp = input()
    table.append(list(tmp))

dfs(0,0,1)

print(answer)