문제:
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력:
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력:
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
풀이방법:
dfs를 사용해서 이 문제를 풀 수 있다. dfs는 다음과 같이 구성되어 있다.
1. 한 점으로부터 시작해 상하좌우를 탐색한다. (처음은 1행 1열)
2. 상하좌우를 탐색할 때, 아직 방문하지 않았고, 처음보는 알파벳이라면 그 방향으로 다시 dfs를 탐색한다.
3. dfs를 시작하는 순간마다. 현재까지 가지고 있는 알파벳 수를 기억해서 최대 몇칸을 지날 수 있는지 확인한다.
4. 더 이상 이동하지 못하는 경우에 한 dfs를 빠져나오게 되며, 방문 기록과 알파벳 탐색 기록을 지운다.
최종적으로 3번을 통해 기록한 값을 출력하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
import sys
input = sys.stdin.readline
def dfs(x,y,tmp):
global answer
if answer < tmp:
answer = tmp
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx < R and 0 <=ny < C:
if not history[ord(alphabet[nx][ny])-65] and not visited[nx][ny]:
history[ord(alphabet[nx][ny])-65] = True
visited[nx][ny] = 1
dfs(nx,ny,tmp+1)
visited[nx][ny] = 0
history[ord(alphabet[nx][ny])-65] = False
R,C = map(int,input().split())
alphabet = []
for _ in range(R):
alphabet.append(list(input()))
visited = [[0 for _ in range(C)] for _ in range(R)]
dx = [-1,0,0,1]
dy = [0,-1,1,0]
history = [False]*26
visited[0][0] = 1
history[ord(alphabet[0][0])-65] = True
answer = 1
dfs(0,0,answer)
print(answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
'Algorithm' 카테고리의 다른 글
| [BOJ]11559. Puyo Puyo (0) | 2021.09.07 |
|---|---|
| [BOJ]3190. 뱀 (0) | 2021.08.19 |
| [BOJ]1520. 내리막길 (0) | 2021.08.17 |
| [BOJ]14425. 문자열 집합 (0) | 2021.06.24 |
| [Programmers]Lv 1.완주하지 못한 선수 (0) | 2019.02.17 |