[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1987번 _ 알파벳

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

1987번: 알파벳

[문제]

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

[입력]

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

[출력]

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

[아이디어]

1) dfs 혹은 bfs로 탐색하되, 동일한 알파벳이 2개 나오면 멈춘다.

2) 알파벳 관리를 set, dict보다 배열로 접근하는 것이 빠르다.

3) 시간초과로 엄청 고생했다. 결론적으로 bfs는 실패다.

4) dfs로 접근시 모든 가능성을 점치기 위해 백트래킹을 실시한다.

import sys
input=sys.stdin.readline

r,c = map(int,input().split())
g = [list(input()) for _ in range(r)]

ans = [0]*26
t = 1
def dfs(x,y,r,c,k):
    global t
    dx = (0,0,1,-1) ; dy = (1,-1,0,0)
    t = max(t,k)
    for i in range(4):
        nx = x+dx[i]; ny = y+dy[i]
        if 0<=nx<r and 0<=ny<c:
            ord_ = ord(g[nx][ny])-65
            if ans[ord_]==0:
                ans[ord_] = 1
                dfs(nx,ny,r,c,k+1)
                ans[ord_] = 0

ans[ord(g[0][0])-65]=1
dfs(0,0,r,c,1)
print(t)

# 시간초과
r,c = map(int,input().split())
g = [list(input()) for _ in range(r)]

def bfs(x,y,r,c,k):
    q = set([(x,y,g[x][y],k)])
    dx = (0,0,1,-1) ; dy = (1,-1,0,0)
    answer = 1
    while q:
        a,b,ans,k = q.pop()
        for i in range(4):
            nx = a+dx[i]; ny = b+dy[i]
            if 0<=nx<r and 0<=ny<c:
                if g[nx][ny] not in ans:
                    q.add((nx,ny,ans+g[nx][ny],k+1))
                    answer = max(answer,k+1)
    return answer
print(bfs(0,0,r,c,1))

로직은 맞지만 중간에 시간초과가 난다.. 이럴땐 파이썬이 싫다 ㅎㅎ