[Python 파이썬]백준 1987번 - 알파벳

2023년 6월 11일

문제 링크 : 1987번 - 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹

---

문제 접근

최대한 길게 뻗어나갈 수 있어야 한다는 키워드를 보고 깊이우선탐색을 사용해야겠다고 생각이 들었다.
경로를 탐색하며 마주치는 알파벳들이 중복되지 않는 선에서 갈 수 있는 최장 거리를 구하면 되는 문제이며, 다음과 같은 방법으로 접근을 시도하려 했다.

• alphas 라는 리스트를 선언, 탐색 과정에서 마주친 알파벳들을 담을 리스트이다.
• dfs를 통해 탐색을 하며 alphas에 알파벳을 append한다. 이 과정에서, 해당 알파벳이 마주친 적 있는(중복된) 알파벳인지 alphas 리스트에서 체크한다.
• 만약 중복되지 않는다면 append를 진행한다.
• 중복된다면 해당 재귀를 탈출하여 백트래킹을 진행한다.

그러나 굳이 alphas 리스트를 선언할 필요가 있나? 생각이 들었다. 깊이 우선 탐색을 진행할 때, 방문여부를 기록하는 visited 리스트를 선언하는데, 이 visited 리스트를 알파벳 개수만큼의 길이로 세팅하는 것이다. 그럼 다음과 같은 흐름대로 진행될 것이다.

• 길이가 26인 visited 리스트를 선언. 초기값은 모두 False이다. 0번째 요소는 'A'를 마주친 적이 있는지부터 나타내며, 마지막 25번째 요소는 'Z'를 마주친 적이 있는지를 나타낸다고 볼 수 있겠다.
• 시작점인 1행 1열의 알파벳이 무엇인지 확인하여, visited의 해당 알파벳 위치 값을 False에서 True로 바꾸어준다.
• dfs를 진행하여 다음 조건에 모두 부합하면 계속 탐색을 진행한다.
  1. 탐색하려는 좌표가 보드의 바운더리 내의 범위이다.
  2. 해당 좌표가 방문한 적 없고, 지금까지 마주친 적 없는 알파벳이다. -> 이는 두 조건을 굳이 걸 필요가 없다. 이미 탐색했던 좌표를 다시 탐색한다는 것 자체가 마주쳤던 알파벳을 한번 더 마주쳤다는 의미와 같기 때문이다.
• 만약 위 조건 중 하나라도 부합하지 않는다면, 백트래킹을 진행한다.
• dfs 탐색을 끝낸 후, 가장 길게 탐색했던 길이를 출력한다.

 

---

순서도

1. R,C를 입력받고, 2차원배열 board를 세팅한다.

2. x축 이동, y축 이동을 정의하는 dx, dy 배열을 선언한다.

3. board를 탐색하며 어떤 알파벳들을 마주쳤는지 정보를 담아둘 visited 리스트 선언. 길이는 알파벳 개수인 26만큼
    3-1. 알파벳들은 대문자 알파벳으로 주어진다. 만약 T라는 알파벳을 마주친 적이 있는지 확인하고 싶다면, visited(ord("T") - ord("A"))로 접근하면 될 것이다.

4. dfs를 이용해 '얼마나 멀리 뻗어나갈 수 있는지'를 탐색한다.
    4.1 중복된 알파벳을 만나거나, board의 인덱스 범위 밖을 벗어나면 백트래킹

 

---

입력 예제

2 4
CAAB
ADCB

순서도에 근거하여 dfs 탐색을 진행한다. 결과는 다음과 같다.

• (1행 1열) - (1행 2열) - (2행 2열) 순서의 C - A - D
• (1행 1열) - (2행 1열) - (2행 2열) 순서의 C - A - D

이 두 경우가 가장 긴 경우이며, 길이는 3이다.

출력 예제

3

---

주의할 점

• 해당 문제 접근이 힘들다면 깊이 우선 탐색과 백트래킹에 대한 이해가 부족하다고 생각된다. 물론 본인도 그랬다. 문제 풀이 과정에 이해가 힘들다면, 두 알고리즘 기법에 대해 조금 공부를 해보고 다시 접근하는 것을 추천한다.
• visited 배열에 접근하기 위해 아스키코드를 이용했다. 각 인덱스 요소들은 'A' 알파벳을 방문했는지에 대한 정보를 담고 있다. dfs 과정에서 마주친 알파벳이 마주쳤던 알파벳인지 확인하기 위해선 적절한 인덱스 접근법이 이용되어야 하는데,  visited[마주친 알파벳의 아스키코드 - 65]로 해당 인덱스를 접근하였다.

---

전체 코드

import sys
input = sys.stdin.readline

def dfs(x,y,cnt):
    global max_cnt
    
    # 지금까지 탐색한 최대 길이가 현재 탐색한 위치까지의 길이보다 작다면, max_cnt를 갱신시켜준다.
    if max_cnt < cnt:
        max_cnt = cnt
    
    for idx in range(4):
        nx = x + dx[idx]
        ny = y + dy[idx]

        # nx,ny가 바운더리를 벗어나지 않는 허용범위 내이고, 지금까지 마주친 적 없는 문자라면 수행한다.
        # 조건에 부합하지 않는다면 탈출 후 백트래킹
        if 0 <= nx < R and 0 <= ny < C and visited[ord(board[nx][ny]) - ord("A")] == False:
            visited[ord(board[nx][ny]) - ord("A")] = True
            dfs(nx,ny,cnt + 1)
            visited[ord(board[nx][ny]) - ord("A")] = False

if __name__ == "__main__":
    # 1. R,C를 입력받고, 2차원배열 board를 세팅한다.
    R,C = map(int,input().split())
    board = []
    for i in range(R):
        board.append(list(map(str,input())))  
        del board[i][-1] 
    # 2. x축 이동, y축 이동을 정의하는 dx, dy 배열을 선언한다.
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 3. board를 탐색하며 어떤 알파벳들을 마주쳤는지 정보를 담아둘 visited 리스트 선언. 길이는 알파벳 개수인 26만큼
    visited = [False] * 26
    
    # 누적 개수(뻗어나간 길이)의 최대값을 담을 max_cnt. 1행 1열에서 시작하기에 초기값은 1
    # board의 1행 1열 알파벳 또한 방문여부 True로 변환
    max_cnt = 1
    visited[ord(board[0][0]) - ord("A")] = True
    
    # 깊이우선탐색 수행. 초기 x,y값은 0,0이며 해당 위치에서 시작하기에 초기값은 1
    dfs(0,0,1)

    # dfs를 통해 최종적으로 산출된 max_cnt 값을 출력한다.
    print(max_cnt)

 

---

풀이 후기

해당 문제는 깊이 우선 탐색과 백트래킹 기법을 어느정도 숙지해야 접근할 수 있다고 본다. 반대로 두 기법에 대해 공부하고 싶다면 해당 문제가 두 기법을 함께 사용하는 가장 일반적인 문제 형태라고 생각하기에, 해당 문제를 통해 부딪혀보며 해결하면 분명 도움이 될 것이라 생각한다.