[BOJ] 1987 알파벳

문제

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

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

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

입력

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

출력

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

 

 

 

처음에 문제를 보자마자 dp와 bfs를 떠올렸고 bfs를 작성했다.

하지만 수많은 시간초과의 벽에 무너졌고, 결국 풀이를 보았다.

풀이는 bfs였는데, 기본적으로 내가 생각한 방향은 맞았다. 하지만 내가 쓴 bfs보다 더욱 효율적인 방법이 있었다.

첫째, 좌표값을 q에 넣는데, q가 평소에 쓰던 list가 아니라 set이어서 중복된 좌표가 자동으로 사라지는것. (set은 기본적으로 정렬)

둘째, 각 위치의 값이 알파벳이라서 방문체크를 별도의 리스트가 될 필요없이 string으로 이어 붙여주는 방식으로 매 순간 방문된 정보를 따로 줄 수 있었던것.

 

이러한 새로운 방법을 알고나니 더욱 효율적으로 bfs코드를 만들 수 있게 된것 같다.

꼭 기억하자.

 

import copy
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
R, C = map(int, input().rstrip().split(" "))
board = []
for _ in range(R):
    board.append(list(input().rstrip()))


d = dict()
for i in range(ord('A'), ord('Z')+1):
    d[chr(i)] = 0  # 0은 미방문, 1은 방문

# 상하좌우
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

answer = 1


def bfs(curr_x, curr_y):
    global d, board, R, C, direction, answer
    q = set()
    q.add((curr_x, curr_y, board[curr_x][curr_y]))
    while(len(q) != 0):
        x, y, s = q.pop()
        for i in range(4):
            new_x, new_y = x+direction[i][0], y+direction[i][1]
            if(new_x >= 0 and new_y >= 0 and new_x < R and new_y < C):
                if(board[new_x][new_y] not in s):
                    q.add((new_x, new_y, s+board[new_x][new_y]))
                    answer = max(answer, len(s)+1)


bfs(0, 0)
print(answer)
# print(res)