[Python] 백준 1987번 문제, 알파벳

<문제 링크>

 

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

1987번: 알파벳

 

---

<풀이>

 

이 문제는 백트래킹을 사용해서 시간을 단축해야 하는 문제이다. 기존 DFS를 수행한다면, 매 경우를 탐색해야 하기 때문에 비효율적이다. 그래서 일정 조건에 부합할 경우 그 위치 p를 저장해 한 턴이 끝났을 때 처음부터 시작하는 것이 아닌 저장해둔 그 위치 p부터 시작한다.

 

예시를 하나 들기 위해 구조가 (1) -> (2) -> (3)처럼 되어 있고 노드가 가진 자식 노드를 dic으로 표현하자면, { (1): 2,  (2): (2-1, 3) }으로 되어 있다고 치자.

그러면 DFS는 3을 향해 간다고 쳤을 때, 2-1를 가기 위해서는 1부터 시작해야 한다.

깊이가 더 깊어진다면 매우 비효율적일 것이다.

따라서 재귀함수를 사용해 3에서 더이상 갈 곳이 없다면 3을 호출한 메소드는 종료하고 3을 호출한 logic(2)로 돌아간다. 그런 다음에 3을 향해 나아갔던 방향말고 다른 방향이 있다면 그 방향을 호출한다.

2는 (2-1, 3)이기 때문에 logic(2-1)을 호출한다. 그래서 3과 마찬가지로 logic(2-1)을 수행한 다음에 갈 곳이 없기 때문에 메소드를 종료하고 2로돌아간다.

logic(2)도 더 이상 호출할 메소드가 없으니 (1)로 돌아가고 (1)도 호출할 번호가 없으니 종료한다.

 

이와 같은 논리로 logic(x, y, visited)를 통해 연산을 수행한다.

(x, y)에 move[]들을 더해 갈 곳이 있다면 탐색을 진행하고 그렇지 않다면 종료한다.

탐색을 진행할 때는 보드 범위를 넘어가지 않거나, 지나온 적이 없는 알파벳이어야 하며, 새로 밟은 알파벳은 visited에 넣어 다음 logic()을 호출할 때 넘겨준다.

 

그리고 메소드가 끝날 때마다 max(max_count, len(visited))를 해주어 최대 경로를 갱신해준다.

 

---

<코드>

borad[][]: (R, C) 보드

move: 상하좌우 이동 리스트

visited: 알파벳을 중복해서 건널 수 없기 때문에 기억하기 위한 리스트

len(visited): 지나온 경로 횟수 저장

---

def logic(x, y, visited): # (x, y), 중복 방지 + 지나온 경로 길이 확인하는 visited
    global max_count # 전역 변수
    limit = 0

    for m in range(4):
        # 좌표 이동
        i = x + move[m][0]
        j = y + move[m][1]

        # 이동 범위를 넘기지 않고, 같은 알파벳이 적힌 칸은 두 번 지나갈 수 없다
        if ((0 <= i < R) and (0 <= j < C)) and (board[i][j] not in visited):
            logic(i, j, visited + board[i][j]) # 다음 방향으로 나아가기
        else:
            limit += 1 # 어떤 방향으로 가려다가 막힘

    if limit == 4: # 이동할 곳이 없다면 이동 값 비교
        max_count = max(max_count, len(visited))


if __name__ == '__main__':
    # init
    R, C = map(int, input().split())
    board = [list(input()) for _ in range(R)]
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # 상우하좌
    max_count = 0 # result

    # logic
    logic(0, 0, board[0][0])

    # print
    print(max_count)