[BOJ-1987] 알파벳

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

1987번: 알파벳

---

[풀이]

이전에 맞았다고했는데, 데이터 추가로 재채점한 결과 틀린 상태가 되어서 다시 풀어보기로 했다.

DFS를 이용해서 풀었다.

MAP의 원소는 A~Z 까지니, 방문리스트 visited의 길이는 26이다.

(* 말이 최대한 움직일 수 있는 횟수는 A~Z까지 26가지란 것을 단박에 알 수 있다)

 

그리고 DFS는 DFS함수를 호출할때마다, 말의 이동횟수의 최댓값을 비교해야한다.

즉, 전역변수 max_alpha와 매개변수 cnt(현재 말이 움직인횟수) 를 비교하여

max_alpha를 업데이트하여 말이 (이동한 위치마다 알파벳이 모두 다르도록)이동한 횟수의 최댓값을 구한다.

 

전역변수 max_alpha=0으로 먼저 초기화했는데

max_alpha가 말이 최대한 (이동할때마다 서로다른 알파벳이 나오도록) 이동한 횟수 이다.

 

 

(1) 초기 (0,0) 위치를 방문해야한다. 

먼저 말은 (0,0)을 당연히 방문을 해야한다.

그래서 (0,0) 위치에 있는 알파벳에 대한 방문리스트 상태를 True로 했다. (visited[MAP[0][0]-'A']=True)

(0,0)위치를 방문했으므로 초기방문횟수는 1로했다.

 

문제의 조건은 말은 이동할때마다, 움직인 곳마다의 알파벳이 모두 달라야한다.

초기 말의 위치에 대한 DFS함수를 호출하면, DFS( 현재Y좌표:0, 현재X좌표:0, 움직인횟수: 1)

 

(2) 말의 현위치의 상/하/좌/우 의 위치가 R행C열 배열에 해당하는 원소인지 확인한다. 

(3) 말의 현위치의 상/하/좌/우 의 위치(nexty, nextx)의 알파벳이 아직 방문하지 않은 상태라면

-> visited[MAP[nexty][nextx] -'A'] =True 로 한다.

-> DFS( nexty, nextx, cnt+1 )

-> 다른 DFS를 호출할때 이미 방문한 곳이 최대방문횟수가 나올 수 있는 경우가 있을 수 있으므로

    DFS호출 후 visited[MAP[nexty][nextx]-'A']를 True로 하자.

---

[코드-python3]

import sys
from copy import deepcopy
input=sys.stdin.readline

dy=(-1,1,0,0)
dx=(0,0,-1,1)
max_alpha=0

def dfs(cury, curx, cnt):
    global MAP,R,C, max_alpha, visited
    max_alpha=max(max_alpha, cnt)
    for i in range(4):
        nexty=cury+dy[i]
        nextx=curx+dx[i]
        if (nexty>=0 and nexty<R) and (nextx>=0 and nextx<C):
            if not visited[ord(MAP[nexty][nextx])-ord('A')]:
                visited[ord(MAP[nexty][nextx])-ord('A')]=True
                dfs(nexty, nextx, cnt+1)
                visited[ord(MAP[nexty][nextx])-ord('A')]=False
                
R,C= map(int, input().strip().split())
MAP=[ [*input().strip()] for _ in range(R)]

visited=[False]*26
visited[ord(MAP[0][0])-ord('A')]=True
dfs(0,0,1)
print(max_alpha)