[ BOJ 1987 ] 알파벳(Python)

문제

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

새로 이동한 칸에 적힌 알파벳은 한번도 지난 적이 없어야 한다.
이 때 최대 몇 칸을 움직일 수 있을지 구하는 문제다.

문제 풀이

알파벳은 26개밖에 되지 않는다.
경우의 수도 최대 400개이니 in 으로 체크해도 되겠다고 생각했다.

집합 자료형을 사용해서 이동하면서 접한 알파벳이 중복되지 않도록 해줬다.

범위 내에서 상하좌우로 이동하면서 알파벳이 겹치지 않으면, (좌표, 이동 거리 + 1, 알파벳)을 집합에 추가해주었다.

가장 큰 이동거리를 저장해준뒤 출력해주었다.

alpha, q = [], set()
q.add((x,y,1,maps[0][0]))
answer = 0

while q:
    x,y,count,alpha = q.pop()
    answer = max(answer, count)

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < R and 0 <= ny < C:
            if (maps[nx][ny] not in alpha):
                q.add((nx,ny,count+1,alpha + maps[nx][ny]))

print(answer)

알게된 점

• set 자료형은 아이템을 추가할 때 add를 사용한다.

코드

import sys
input = sys.stdin.readline

R, C = map(int,input().rsplit())
maps = [[] for _ in range(R)]

for i in range(R):
    maps[i] = list(input().rstrip())

x, y = 0, 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]

alpha, q = [], set()
q.add((x,y,1,maps[0][0]))
answer = 0

while q:
    x,y,count,alpha = q.pop()
    answer = max(answer, count)

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < R and 0 <= ny < C:
            if (maps[nx][ny] not in alpha):
                q.add((nx,ny,count+1,alpha + maps[nx][ny]))

print(answer)