📜 문제 이해하기
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
💡 문제 재정의
주어진 알파벳 보드에서 (0, 0)에서 시작할 때 알파벳이 겹치지 않도록 이동할 수 있는 최대 길이를 구하여라.
✏️ 계획 수립
이 문제는 (0, 0)부터 dfs를 하면서 방분하지 않았던 알파벳 방향으로 진행하면서 가장 큰 길이를 찾으면 되는 문제이다. 방문하지 않은 알파벳을 알기위해 alphabets라는 배열을 사용하여 방문했다면 1 방문하지 않았다면 0으로 표시하였고 방문이 종료되었다면 0으로 다시 만들어 주었다. 배열을 하나만 써도 되는 이유는 어차피 같은 알파벳은 방문하지 않는다는 가정이 있기 때문이다. 이때 알파벳의 아스키코드에서 65를 뺀 값을 index로 활용하였다.
💻 계획 수행
import sys
max_count = 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
alphabets = [0 for i in range(26)]
tiles = []
R = 0
C = 0
def dfs(y, x, count):
global max_count
max_count = max(max_count, count + 1)
for d in directions:
next_y = y + d[0]
next_x = x + d[1]
if 0 <= next_y < R and 0 <= next_x < C:
alpha_idx = ord(tiles[next_y][next_x]) - 65
if not alphabets[alpha_idx]:
alphabets[alpha_idx] = 1
dfs(next_y, next_x, count + 1)
alphabets[alpha_idx] = 0
if __name__ == '__main__':
R, C = map(int, sys.stdin.readline().split())
for _ in range(R):
tiles.append(list(map(str, sys.stdin.readline()[:-1])))
alphabets[ord(tiles[0][0]) - 65] = 1
dfs(0, 0, 0)
print(max_count)🤔 회고
그래프를 구현하는건 어렵지 않았지만 시간 초과가 계속 발생했다. 처음에는 알파벳을 set으로 관리하여 in 연산자로 탐색했지만 파이썬에서는 탐색하는순간 시간 초과에 걸렸다. 결국 alphabet이 26개밖에 안되기때문에 리스트를 만들고 아스키 코드를 활용해 상수 시간에 접근함으로써 문제를 해결하였다. 메모리를 많이 사용하여 시간을 줄이는 연습을 많이 겪어봐야 이런 아이디어가 빠르게 떠오를 것 같다.
