[🥇4 / 백준 1987 / 파이썬] 알파벳

 

1987번: 알파벳

 

문제

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

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

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

입력

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

출력

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

 

예제 입력 1  2 4 CAAB ADCB	예제 출력 1  3
예제 입력 2  3 6 HFDFFB AJHGDH DGAGEH	예제 출력 2  6
예제 입력 3  5 5 IEFCJ FHFKC FFALF HFGCF HMCHH	예제 출력 3  10

 

풀이

 

DFS 혹은 BFS로 알파벳을 겹치지 않게 이동하는 문제이다.

 

DFS를 할 경우 보드의 알파벳들을 모두 아스키 코드로 바꿔준 뒤에 진행하는 것이 좋다.

그리고 알파벳 26개의 방문 여부를 담는 배열을 하나 만들어준 뒤, 해당 보드의 아스키 코드를 가져와 방문 여부를 표시한다.

 

DFS의 경우 PyPy3 로 제출해야 풀렸다.

 

import sys
input = sys.stdin.readline

r,c = map(int,input().split())
board = [list(input().rstrip()) for _ in range(r)]
# 아스키 코드로 변환
for i in range(r):
    for j in range(c):
        board[i][j] = ord(board[i][j])-65

move = [(0,1),(1,0),(0,-1),(-1,0)]
result = 0; ch_list = [0]*26
def dfs(x,y,cnt):
    global result
    result = max(result,cnt)
    if result == 26:
        print(result)
        sys.exit()
    
    if ch_list[board[x][y]] == 0:
        ch_list[board[x][y]] = 1
        for a,b in move:
            dx=x+a; dy=y+b
            if r>dx>=0 and c>dy>=0:
                dfs(dx,dy,cnt+1)
        ch_list[board[x][y]] = 0
            
dfs(0,0,0)
print(result)

 

BFS로는 Queue 대신 Set 형을 이용해야 시간 초과를 면할 수 있었다.

어차피 최단 거리를 찾는 것이 아니기 때문에 굳이 큐가 아니어도 상관이 없었다.

무엇보다 중복된 원소를 처리하는 데에 편하다.

 

BFS를 진행할 땐 굳이 아스키 코드로 변환하지 않고 큐의 원소마다 지나온 문자열들을 따로 넣어주었다.

 

이상했던게, BFS의 경우 PyPy3 보다 Python3 로 제출하는 것이 시간이 훨씬 적게 들었다.

원래 PyPy가 파이썬보다 일반적으로 빠르다고 알고 있었기 때문에 정말 요상했다.

 

import sys
input = sys.stdin.readline

def bfs():
    r,c = map(int,input().split())
    board = [list(input().rstrip()) for _ in range(r)]

    move = [(0,1),(1,0),(0,-1),(-1,0)]
    result = 0
    q = set([(0,0,board[0][0])])
    while q:
        x,y,ch_list = q.pop()
        result = max(result,len(ch_list))
        if result==26:
            return 26

        for a,b in move:
            dx=x+a; dy=y+b
            if r>dx>=0 and c>dy>=0 and board[dx][dy] not in ch_list:
                q.add((dx,dy,ch_list + board[dx][dy]))
    return result
print(bfs())