문제

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

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

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

www.acmicpc.net/problem/1987

  • 입력

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

  • 출력

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

과정

쉬워보여서 “이것만 빨리 풀고 자야지~” 했다가 큰 코 다쳐벌인 문제.

이전 문제를 dfs로 풀어서 이번 문제도 dfs로 풀어봐야지~ 하고 제출했는데 시간초과를 얻었다. 뭐가 잘못됐는지 블로그의 다른 풀이들을 뒤져봐도 답이 안 나와서 아예 복붙까지 해봤는데 도저히 dfs로는 답이 안 나왔다;. 심지어 알고리즘 분류에도 ‘깊이 우선 탐색’이 있는데 그새 문제 조건이라도 바뀐건지ㅜ. 시간을 엄청 쏟았지만 dfs로는 안 되겠다 싶어서 포기하고 bfs로 넘어갔다. 메모이제이션을 해줘야하는걸까? 모르겠다.

import sys

def dfs(x, y, cur):
    global res
    # 최댓값 갱신
    res = max(res, cur)
    # 상하좌우 탐색
    for dx, dy in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
        nx, ny = x + dx, y + dy
        # 좌표가 범위 안이고, 아직 방문하지 않은 알파벳인 경우
        if 0 <= nx < r and 0 <= ny < c and alphabet[board[nx][ny]] == False:
            alphabet[board[nx][ny]] = True
            # 계속 탐색
            dfs(nx, ny, cur + 1)
            alphabet[board[nx][ny]] = False

r, c = map(int, sys.stdin.readline().split())
# 방문한 알파벳을 배열로 확인하기 위해 알파벳을 아스키코드 숫자로 변경하여 저장한다
board = [list(map(lambda x: ord(x) - 65, list(sys.stdin.readline().strip()))) for _ in range(r)]
# 방문한 알파벳을 확인하기 위한 배열
alphabet = [False] * 26
alphabet[board[0][0]] = True
res = 1

dfs(0, 0, 1)
print(res)

최종 코드

결국 bfs로 코드를 수정했는데, 한 가지 더 유의할 점이 있었다. deque 대신 set 자료구조를 이용해야 시간초과를 피할 수 있다. set에는 좌표와 현재까지 방문한 알파벳이 들어가는데 중복을 피하기 위해 deque가 아닌 set을 사용해야 한다.

또 불필요한 탐색을 줄이기 위해 모든 알파벳을 방문한 경우 탐색을 종료하도록 했다. 나머지는 일반적인 bfs와 같았다.

하지만 이번엔 또 python3에서는 통과하는데 pypy3에서는 시간초과가 떴다. 하..

import sys

def bfs():
    ret = 1
    # 중복을 피하기 위해 deque 대신 set 사용
    s = set()
    # 방문한 알파벳은 문자열로 저장
    s.add((0, 0, board[0][0]))

    while s:
        x, y, alphabet = s.pop()
        ret = max(ret, len(alphabet))
        # 모든 알파벳을 방문한 경우 탐색 종료
        if ret == 26:
            break

        for dx, dy in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
            nx, ny = x + dx, y + dy
            if 0 <= nx < r and 0 <= ny < c and board[nx][ny] not in alphabet:
                s.add((nx, ny, alphabet + board[nx][ny]))

    return ret

r, c = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().strip()) for _ in range(r)]

print(bfs())

Enhanced

다른 분들의 코드와 비교해보다가 설마했는데 dx, dy를 zip이 아니라 따로 배열을 선언해서 for loop을 도니까 pypy3에서도 통과가 되었다. 정말 보기보다 시간관리 차원에서 까다로운 문제여서 너무 힘들었다ㅠㅠ.

import sys
# 시간을 줄이기 위해 dx, dy 배열을 따로 선언한다
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def bfs():
    ret = 1
    # 중복을 피하기 위해 deque 대신 set 사용
    s = set()
    # 방문한 알파벳은 문자열로 저장
    s.add((0, 0, board[0][0]))

    while s:
        x, y, alphabet = s.pop()
        ret = max(ret, len(alphabet))
        # 모든 알파벳을 방문한 경우 탐색 종료
        if ret == 26:
            break

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < r and 0 <= ny < c and board[nx][ny] not in alphabet:
                s.add((nx, ny, alphabet + board[nx][ny]))

    return ret

r, c = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().strip()) for _ in range(r)]

print(bfs())

참고 사이트