백준 1987 알파벳

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

1987번: 알파벳

처음에 온갖 똥고쇼를 해도 시간초과를 피할 수 없었다.

그나마 줄일대로줄여서 pypy로 간신히 맞았다.

import sys

input=sys.stdin.readline
move=((-1,0),(1,0),(0,-1),(0,1))
answer=1


def dfs(next,value):
    global answer
    answer=max(answer,value)
    i,j=next
    for a,b in move:
        ti,tj=i+a,j+b
        if 0<=ti<r and 0<=tj<c and arr[ti][tj] not in visited :
            visited.add(arr[ti][tj])
            dfs((ti,tj),value+1)
            visited.remove(arr[ti][tj])

    




r,c=map(int,input().split())
arr=[list(input().strip()) for _ in range(r)]
visited=set(arr[0][0])

dfs((0,0),1)
print(answer)

그후 다른사람들의 풀이를 보니 bfs로 푸는 방법이 있었다.

import sys
input=sys.stdin.readline

def bfs(i=0,j=0):
    global answer
    q=set([(i,j,arr[i][j])])
    while q:
        i,j,ans=q.pop()
        for a,b in move:
            ti,tj=i+a,j+b
            if 0<=ti<r and 0<=tj<c and arr[ti][tj] not in ans:
                q.add((ti,tj,ans+arr[ti][tj]))
                answer=max(answer,len(ans)+1)
    print(answer)


move=((-1,0),(1,0),(0,-1),(0,1))
answer=1
r,c=map(int,input().split())
arr=[list(input().strip())for _ in range(r)] 
bfs()

솔직히 아직 잘 이해 못하겠지만

대충 set으로 중복을 방지하고, bfs를 진행하며, ans가 최대점인 값을 찾는다.

다음에다시풀어봐야겠다.