728x90
반응형
문제 내용
시간 제한 : 2 초
메모리 : 256 MB
공간
- RxC 크기의 공간 (각 좌표마다 알파벳 쓰여있음)
등장인물
- 말 : (1,1) 위치에 놓여있음
동작
말을 상하좌우로 이동한다. 아래의 제약 조건 있음.
- 각 알파벳을 2번 이상 밟고 지나갈 수 없음.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)
둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
예제 입력 1
2 4
CAAB
ADCB
예제 출력 1
3
유형
풀이
전형 적인 탐색 문제에 약간의 테크닉이 첨가되어야 하는 문제다.
각 알파벳을 2번 이상 밟고 지나갈 수 없으면서 최대한 많은 칸을 밟아야 한다.
즉, 각 위치를 여러가지 경로로 중복해서 방문할 수 있다는 가능성을 열어 두어야 한다.
예를 들면 (2,2) 위치를
A-B-C 로도 올 수 있고, A-C-B 로도 올 수 있다.
문제는 중복 방문을 허용하게 되면 시간과 메모리를 많이 잡아 먹는다.
그래서 중복 검사를 아주 효율적으로 해야하는 테크닉이 필요하다.
- visited (방문 검사 배열) 에 경로 자체를 저장한다.
해당 위치에 다른 경로로 도달했을 경우에만 갱신하고 큐 또는 리스트에 넣는다. - 문자열 (str, 텍스트 시퀀스)의 +연산은 실제로 새로운 str 객체를 생성해야 되는 방식이므로
꽤 많은 시간을 잡아먹는다. 따라서 문자열 그대로 저장하지 않고 비트로 변환하여 저장한다.
A-B의 경우 'AB'로 저장하지 않고 2진수 11로 저장되는 방식이다.
import sys
r,c = map(int,sys.stdin.readline().split())
board = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
visited = [[[] for _ in range(c)] for _ in range(r)]
result = 0
dx = (-1,1,0,0)
dy = (0,0,1,-1)
A = ord('A')
q = ([(0,0,1,1<<(ord(board[0][0])-A))])
while q and result < 26:
x, y, cnt, cur_bit = q.pop()
result = max(result, cnt)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0<= ny <c:
seq = ord(board[nx][ny])-A
if cur_bit & (1<<seq) == 0 :
next_bit = cur_bit | 1<<seq
if visited[nx][ny] != next_bit:
visited[nx][ny] = next_bit
q.append((nx,ny,cnt+1,next_bit))
print(result)
반응형
'Python > 백준 문제풀이' 카테고리의 다른 글
파이썬(python) 백준 1966 : 프린터 큐 (1) | 2022.09.25 |
---|---|
파이썬(python) 백준 16236 : 아기 상어 (2) | 2021.05.25 |
파이썬(python) 백준 14496 : 그대, 그머가 되어 (0) | 2021.05.19 |
파이썬(python) 백준 2206 : 벽 부수고 이동하기 (0) | 2021.05.02 |
파이썬(python) 백준 7576 : 토마토 (0) | 2021.05.01 |