[BOJ][🟡4][백준#01987] 알파벳

문제 출처

BAEKJOON Online Judge #1987

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

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

출력

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

예제

예제 1

입력

2 4
CAAB
ADCB

출력

3

예제 2

입력

3 6
HFDFFB
AJHGDH
DGAGEH

출력

6

예제 3

입력

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

출력

10

My Sol

maxCnt = 0
I, J = map(int, input().split())
mat = [list(input()) for _ in range(I)]
visits = [[[] for _ in range(J)] for _ in range(I)]
visits[0][0].append((1, 0^(1<<(ord(mat[0][0])-65))))

cntSet = set()
Q = set()
Q.add((0, 0))

while Q:
    ni, nj = Q.pop()
    while visits[ni][nj]:
        cntNow, visit = visits[ni][nj].pop()
        needCnt = 1
        for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
            si, sj = ni+di, nj+dj
            if not (0<=si<I and 0<=sj<J): continue
            if visit&(1<<(ord(mat[si][sj])-65)): continue
            needCnt = 0
            visits[si][sj].append((cntNow+1, visit|(1<<(ord(mat[si][sj])-65))))
            Q.add((si, sj))

        if needCnt:
            maxCnt = max(maxCnt, cntNow)
print(maxCnt)

메모리와 시간 모두 고려해야 했던 문제였다. 각 알파벳을 ord로 ASCII문자 숫자로 바꾼 뒤, 비트마스킹을 사용해 visit에 저장하였다. 즉, A라면 0번째, B라면 1번째 체크를 매 좌표마다 두었고, 매번 수를 세지 않기 위해 탐색 좌표가 visit이 가능하다면 cnt를 1 추가한 값과 함께 visit 체크하여 tuple로 저장하였다.

탐색 좌표에서 또 주변 인접 좌표로 visit할 수 있는지 확인해야하므로 Q에 집어넣고 Q에서 매번 좌표를 꺼내서 인접 좌표로 이동할 수 있는지 확인하다가 결국 모든 Q에서 이동할 수 있는 좌표가 없다면 종료하는 것이다.

어떤 기준점에서 상하좌우 인접 좌표를 모두 visit할 수 없다면 needCnt가 0으로 갱신되지 않아 maxCnt를 cntNow와 비교하여 갱신해준다.

어려웠던 점

탐색 좌표를 Q에 추가하는 과정에서 깊이가 깊어질수록 중복되는 좌표들이 많아졌고, 최초 deque를 사용했던 것을 set으로 바꾸어 add와 pop 해주었다. deque를 사용하면 popleft를 사용할 수 있지만, 굳이 추가된 순서대로 할 필요 없이 Q가 존재하는동안만 진행하면 되므로 중복좌표를 획기적으로 줄일 수 있는 방법이었다.

그리고 최초에는 visits의 각 좌표에 visit할 수 있으면 visit 체크 후 visit만 추가하였다. 그런데 상하좌우로 이동할 수 없을 때 visit의 각 자리의 1이 있다면 cnt를 1 올리고 toggle 하며 비트방식으로 cnt를 센 뒤에, visit이 0이 되면 cnt를 maxCnt와 비교하는 방식을 사용하였다. 그런데 visit이 많아지면서 시간 초과의 주범이 되었고, tuple 방식으로 cnt를 한 번에 maxCnt와 비교하여 갱신하도록 하였다.

결과

맞았습니다!!

모범답안

출처

import sys

read = sys.stdin.readline
R, C = map(int, read().split())
graph = [read().strip() for _ in range(R)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def bfs(a, b):
    q = {(a, b, graph[a][b])}
    check = [['' for _ in range(C)] for _ in range(R)]
    check[a][b] = graph[a][b]
    result = 1
    while q:
        x, y, track = q.pop()
        result = max(result, len(track))
        if result == 26:
            break
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 좌표 nx, ny을 기준으로 (현재 위치에 저장되어 있는 결과 와 이전 결과 + graph 현재 위치) 가 다르다면
            # check nx, ny에 결과를 저장한다.
            if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] not in track and check[nx][ny] != track + graph[nx][ny]:
                check[nx][ny] = track + graph[nx][ny]
                q.add((nx, ny, check[nx][ny]))
    return result


print(bfs(0, 0))

연산시간이 획기적으로 짧은 풀이를 발견하여 분석한다. 역시 q는 set을 이용하여 추가해주었다. 문자열을 붙여가며 붙여온 경로 문자열 내에 탐색 좌표의 문자열이 없는 경우를 not in을 이용해 확인해주었다.

인상적인 부분은 탐색 좌표에 visit할 수 있다면 해당 좌표의 값까지 경로에 붙여 갱신해주는데, 이미 다른 경로로 해당 좌표에 저장이 되어있던 경우 경로가 매번 다른데 check에 덮어씌워도 되는가 하는 생각이 든다.