https://www.acmicpc.net/problem/1987
1987번: 알파벳세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으www.acmicpc.net
처음에 온갖 똥고쇼를 해도 시간초과를 피할 수 없었다.
그나마 줄일대로줄여서 pypy로 간신히 맞았다.
import sysinput=sys.stdin.readlinemove=((-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 sysinput=sys.stdin.readlinedef 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=1r,c=map(int,input().split())
arr=[list(input().strip())for _ in range(r)] bfs()솔직히 아직 잘 이해 못하겠지만
대충 set으로 중복을 방지하고, bfs를 진행하며, ans가 최대점인 값을 찾는다.
다음에다시풀어봐야겠다.