[BOJ] 1987번 : 알파벳 (백트래킹, DFS, BFS)

접근

문제 자체는 복잡해보이지 않았다. 지나온 알파벳은 다시 들리지 않는다. 이게 이 문제의 중점이었던 것 같은데, 나는 백트래킹 최적화에 애를 먹어서 몇가지 기억하려고 남기려한다.

 

해결

사실 백트래킹 방법이 아니라, 충분히 BFS로 풀 수 있어보이지만 그냥 앞서서 N과M 문제 풀다보니, 백트래킹으로 해결하려고 시간을 썼다. 근데... 자꾸만 시간 초과가 나서 몇가지 최적화를 진행했다.

 

일단 백트래킹에 대해서 잠깐 서술해보자면, 영어 그대로 Back Tracking이다.

백트래킹은 재귀적으로 접근하는 알고리즘이다. 모든 경우를 고려하며, 재귀적으로 탐색을 진행하다가 특정 조건에 맞지않는 경우를 제외하고, 다시 탐색을 진행하는 것이다.

 

DFS를 재귀로 구현할 때를 생각하면 형태가 거의 비슷하여 알고리즘의 이해에 대한 문제점은 많이 없을 것이라 생각한다.

아래는 백트래킹 연습용으로 좋은 N과 M 예제들이다.

 

[백트래킹 연습용 문제]

• N과 M (5) : https://www.acmicpc.net/problem/15654
• N과 M (9) : https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

15654번: N과 M (5)

---

다시 각설하고, 알파벳 문제로 돌아와보자.

알파벳 문제는 지나온 알파벳을 체크하는 것으로 아마 경우의 수를 제거해나갈 것이다.

혹은 더 이상 진행할 곳이 없다면, 그 경우도 끝을 내는 방향으로 제거할 것이다.

이 부분에서 나는 최적화 문제가 발생했다.

일반적으로 나는 방문 노드를 체크할 때 'collections' 라이브러리의 'defaultdict'를 이용하는데, 도대체 어떻게 해도 시간초과가 나는 것이다. 그래서 질문게시판 탐방을 하다가, 'dict'가 아니라 'set'로 하면 통과가 된다는 말을 보고, 한번 'set'로 바꾸니까 바로 통과가 됐다. 마음이 아팠다.

알고리즘 문제인가 해서 백트래킹 알고리즘 최적화를 진행했는데, 오히려 시간초과 발생이 더 빨리 됐었기에 시간을 조금 낭비했다.

그래서 시간초과 체크리스트를 만들어둘까 해서 이 글을 작성하기로 마음 먹었다.

 

시간초과 체크리스트

• 입력의 갯수가 많은가? => 빠른입출력 사용('sys.stdin.readline')
  • 빠른 입출력 사용은 조심해서 하자. 'strip'으로, 양끝단의 개행문자를 제거해주는 작업을 꼭 수행하자.
• 방문 체크
  • 방문만 체크할거면, 'set'형 사용
  • 방문과 다른 특정 조건(value로 조건을 파악하자)을 체크해야한다면, 'dict'형 사용
• 알고리즘 자체의 문제
  • 시간복잡도를 고려하자. 처음 시도부터 효율적인 알고리즘을 사용하는게 가장 최선이지만, 바로 떠오르지 않을 수 있다. 그럼 해당 알고리즘의 효율적 구현은 어떻게 했는지 잘 구분해두자.
    • 예) 다익스트라 구현 => 전체탐색 > Heap
• 백준한정
  • Python 안되면, Pypy3로 제출해보자.

코드

import sys

input = sys.stdin.readline

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

boards = []
for _ in range(R):
    tmp = []
    for c in input():
        alpha_sort.add(c)
        tmp.append(c)
    boards.append(tmp)
    
dy = [0, 0, -1, 1]
dx = [-1, 1, 0, 0]
max_cnt = 0
visited = set()
visited.add(boards[0][0])

def dfs(st, cnt, visited):
    global max_cnt
    
    max_cnt = max(max_cnt, cnt)
    y, x = st
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < R and 0 <= nx < C:
            if not boards[ny][nx] in visited:
                visited.add(boards[ny][nx])
                dfs([ny, nx], cnt+1, visited)
                visited.discard(boards[ny][nx])  
    return


dfs([0, 0], 1, visited)
print(max_cnt)