BOJ 1987번: 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

아이디어:

백트래킹과 DFS를 사용하여 구현하였다. 내가 이해한 방식이 맞는 지는 모르겠지만.. 일단 재귀함수로 구현하였고, pypy로 통과했다.

조건은 크게 어렵지 않았던 것 같다. 차근차근히 풀면 풀어졌다.

최댓값을 갱신하는 부분과, DFS에서 돌아온 후에 True를 다시 False로, cnt--를 해주는 것에 유의하자. (이 부분을 if문 밖에 써서 삽질을 했었다.) + 좌표 범위 체크하는 조건도!

 

 

#1987번 알파벳
import sys

R, C = map(int, sys.stdin.readline().split())
visit = [False]*26
board = [['0'] for _ in range(R+1)]
board[0] = ['0']*(C+1)
for i in range(1,R+1):
    board[i]+=list(sys.stdin.readline().rstrip())

xx = [1, -1, 0, 0]
yy = [0, 0, 1, -1] #상하좌우 움직이는 x,y좌표

cnt = 0
ans = 0

def DFS(X, Y):
    global cnt, ans
    cnt+=1
    ans = max(ans, cnt)
    r,c = Y,X
    visit[ord(board[r][c])-65] = True
    
    for i in range(4):
        x = c + xx[i]
        y = r + yy[i]
        if (x>=1 and x<=C and y>=1 and y<=R): #범위 체크
            if (visit[ord(board[y][x])-65]==False):
                visit[ord(board[y][x])-65] = True
                DFS(x,y)
                visit[ord(board[y][x])-65] = False
                cnt-=1
DFS(1,1)
print(ans)