백준 1987 알파벳

import sys
from collections import deque

n,m=map(int,sys.stdin.readline().split())
graph=list()
dir=[[-1,0],[1,0],[0,-1],[0,1]]

for _ in range(n):
    graph.append(list(sys.stdin.readline().rstrip()))

alpha=set()
alpha.add(graph[0][0])
ans=0

def dfs_recur(x,y,count):
    global ans
    ans=max(ans,count)

    for i in range(4):
        dx=x+dir[i][0]
        dy=y+dir[i][1]

        if dx>=0 and dx<n and dy>=0 and dy<m and graph[dx][dy] not in alpha:
            alpha.add(graph[dx][dy])
            dfs_recur(dx,dy,count+1)
            alpha.remove(graph[dx][dy])


dfs_recur(0,0,1)
print(ans)

링크텍스트

알파벳 문제이다.

2 4

CAAB

ADCB

n,m 은 각각 세로와 가로의 길이를 나타내고 밑은 들어있는 알파벳을 말한다.

graph[0][0] 인덱스에서 시작하여 서로다른 수만 나오는 경우를 따젔을때 가장 긴 경우를 결과로 내는것이 목적이다.

나는 dfs 와 bfs 를 섞어서 사용하였는데

C 에서 시작하여 인접해 있는 값들을 비교해주어 alpha 라는 리스트에 없으면 추가하고 있으면 추가하지 않는 방식이다.

​

CAAB

ADCB 가 있을때 C는 초기 수임으로 alpha 에 넣은뒤 C 에서 부터 BFS 를 시작한다. C에서 갈수있는 방향은 오른쪽 A 그리고 바로 밑 A 이다.

오른쪽 A 부터 가게 된다면 A가 alpha 에 있는지 확인후 alpha에 없으면 alpha에 넣은후 또 거기서 BFS 를 진행한다.그럼 A 바로 밑인 D로 가게되고 그 후론 갈수있는곳이 없어서 max는 3이 될것이다.

하지만 우리는 돌아가면서 모든 가능한 방향을 찾아봐야한다. 그렇기에 돌아가면서는 초기값으로 돌려놔야한다.

그래서 재귀가 끝나면 alpha.remove(graph[dx][dy])를 해준것이다.