(알고리즘) 백준 1987번 python 파이썬

문제

오늘 풀어본 문제는 백준 1987 알파벳 문제이다.
먼제 문제를 살펴보자
https://www.acmicpc.net/problem/1987

풀이방법

해당 문제는 그래프탐색문제로 볼 수 있다.
좌측 상단 0,0의 지점부터 탐색을 해 나가면서 상하좌우로 움직 일 수 있다.
이때 탐색 가능한 조건은 이전에 방문했던 곳의 글자와 일치하지 않는 곳으로만 방문할 수 있다.
해당 조건을 위해 dfs로 코드를 구현하며 지금까지 방문해온 문자를 문자열 매개변수로 넘겨주면서 다음 노드 방문을 할지 말지 탐색하면 된다

코드

Y,X=map(int,input().split(' '))

pan=[] #지도를 저장할 변수
for _ in range(Y):
    pan.append(input())
ans=0#최대 길이
def dfs(y,x,before):#죄표와 이전에 방문했던 문자열을 변수로 준다
    global ans
    dx=[0,0,1,-1]
    dy=[-1,1,0,0]
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if(0<=ny<Y and 0<=nx<X and pan[ny][nx] not in before):#다음 방문할 곳의 문자열이 이전 문자열에 없으면
            dfs(ny,nx,before+pan[ny][nx])#방문한다
    if(len(before)>ans):#현재 값이 이전 최대 값보다 길면 정답을 현재의 길이로 치환
        ans=len(before)

dfs(0,0,pan[0][0])#0,0부터 방문

print(ans)

후기

어려운 문제는 아니였다. 다만 본인의 경우 DFS를 활용했는데 BFS를 활용 할 경우 속도가 훨씬 빨라졌다.
BFS가 빠를지 DFS가 빠를지 감을 잡는 연습을 더 많이 해야겠다.