[Baekjoon 1987 / Python / 골드4] 알파벳

문제

 

DFS, 백트래킹 문제이다. 상하좌우 탐색을 요하기 때문에 BFS로도 잠시 생각했었으나 백트래킹이 필요했기에 DFS로 진행했다. 어느정도 정석에 가까운 백트래킹 문제 같다.

 

# DFS, 백트래킹

import sys

input = sys.stdin.readline

# 입력받기

R, C = map(int, input().split())

board = []

for _ in range(R):

    board.append(list(input().strip()))

# 사전준비

directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

visited = [[False] * C for _ in range(R)]

visited[0][0] = True

path = set() # 집합으로 불필요한 중복 알파벳이 들어가는 것을 방지

result = 1

# DFS로 모든 경로의 깊이를 탐색후 최대 깊이 갱신하는 함수

def backTracking(x, y, depth):

    global result

    path.add(board[x][y]) # 경로에 알파벳 추가

    result = max(result, depth) # 최댓값 갱신

    # 4방향 체크

    for di in directions:

        nx, ny = x + di[0], y + di[1]

       

        # 갈수있으면 재귀

        if goingNoGoing(nx, ny):

            visited[nx][ny] = True

            backTracking(nx, ny, depth + 1)

            visited[nx][ny] = False

   

    path.remove(board[x][y]) # 돌아가기 전 경로에서 알파벳 빼주기

# 다음 좌표가 유효한지 확인하는 함수

def goingNoGoing(nx, ny):

    # board안에 있고, 겹치는 알파벳 아니고, 아직 방문 안했을 경우 True

    if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in path and not visited[nx][ny]:

        return True

    return False

# 정답 출력

backTracking(0, 0, 1)

print(result)

 

우선 입력받는 알파벳을 그래프화하여 노드 취급한다.

 

DFS를 하기 위해선 인접 노드를 가리키는 인접 리스트를 작성해야 하는데, 어차피 행렬 형태로 이루어진 그래프이기 때문에 모든 노드가 똑같이 상/하/좌/우의 4방향 인접 노드를 가진다. 물론 가장자리에 있는 노드들은 아니겠지만, 조건문으로 걸러주면 된다.

 

backTracking 함수가 한번 호출될 때마다 해당 위치를 방문체크하고 알파벳을 path에 넣어준다. 그리고 다음 좌표에 갈 수 있는지 확인 후 재귀호출 해주면 된다. 재귀호출이 끝났다면 방문체크를 False로 되돌려 놓고 알파벳도 없애주면 된다.

이렇게 가능한 경우의 수를 모두 탐색하되 가능성 없는 경로는 배제하며 백트래킹을 진행할 수 있다.

 

다만 메모리랑 시간을 좀 많이 먹긴 한다. 이 코드는 pypy3으로 제출할 때만 통과되고 python3은 시간 초과가 난다.

또한 path를 set()이 아닌 일반 리스트로 선언 후 append와 pop으로 구현해도 시간 초과가 난다. 알파벳은 해봤자 26개밖에 안되고, 그러므로 최대 경로 길이는 26이므로 path에 현재경로 알파벳이 있는지 확인하는 not in 연산은 크게 의미 없을거라 생각하는데, set()을 쓰지 않으면 시간 초과라는 것을 고려해 보면 아마 턱걸이로 통과한 코드가 아닐까 싶다.

 

내가 못한건가 싶어 다른 사람들 채점 현황도 확인해 봤는데 python3으로 통과된 사람은 거의 없긴 했다. 조금 다행이다.

 

 

결과