[python] 백준 - 1987. 알파벳

 

출처 : BACKJOON ONLINE JUDGE

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

1987번: 알파벳

 

문제 해결

1. DFS/BFS 를 활용하는 방법과 백트래킹을 활용하는 방법 중 하나를 사용하면 된다.

( 여기서는 백트래킹을 사용했다. )

2. 함수 인자로 ( x좌표, y좌표, 지나가면서 늘어가는 단어) 이 3개를 받는다.

3. 상하좌우 방향을 탐색하면서, 이미 가지고 있는 단어에 포함되어 있는 문자인지 확인해주고

4. 한칸씩 전전할 수 있는 모든경우의 수를 포문으로 돌려가면서 확인해준다.

 

- > python 으로 제출 시 시간 초과가 나와서, pypy로 제출해서 통과했다.

+  BFS를 사용하는게 시간이 더 절약된다.

소스코드

def backt(x, y, word):
    global result
    check = 0
    for k in range(4):  # 상 하 좌 우 4방향 탐색
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < n and 0 <= ny < m and words[nx][ny] not in word:  # 인덱스 초과 방지 & 문자 중복 방지
            backt(nx, ny, word+words[nx][ny])
        else:
            check += 1

    # 더 이상 이동할 수 없으면 문자의 길이를 확인해 준다.
    if check == 4:
        result = max(result, len(word))
        return


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m = map(int, input().split())  # R, C | 세로, 가로
words = [list(input()) for _ in range(n)]
result = 0
backt(0, 0, words[0][0])
print(result)