[백준] No.1987 알파벳 01

골드 2에서 골드 1로 승급하게 해 준 문제

 

1987번: 알파벳

DFS로 판을 탐색하면서 모든 경우의 수를 탐색하고, 최댓값을 찾는 문제다.

일반적인 백트래킹 문제라고 생각하여 접근했는데, 꽤나 틀려서 글을 작성한다.

제발 기본에 집중하자 기본에.

 

# ---------- Function ----------
def DFS(x, y, cur_move):
    global max_move
    max_move = max(max_move, cur_move)
    
    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy
        
        if 0 <= nx < row and 0 <= ny < col and graph[nx][ny] not in alphabet:
            alphabet.add(graph[nx][ny])
            DFS(nx, ny, cur_move+1)
            alphabet.remove(graph[nx][ny])
            
# ---------- Main ----------
row, col = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(row)]

alphabet = set()
alphabet.add(graph[0][0])

dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

max_move = 1
DFS(0, 0, 1)

print(max_move)

처음에 작성하고 조금 다듬은 코드이다.

골드 4에 백트래킹, 시간 제한 2초에 정답 비율 29.316%을 보고 시간에 유의해야 겠다 생각했다.

접근법은 이러하다.

우선 지나는 알파벳들의 종류는 중복해서 지나서는 안 된다. 또한 시간에 유의해야 한다.

list로 저장해서 not in list로 확인할 수 있지만, 이건 시간복잡도가 O(n)이 걸린다.

하지만 set은 중복을 피하는 저장이 가능하고 not in set을 사용하면 시간복잡도가 O(1)이다.

이점을 감안하여 처음부터 set() 자료구조를 선택했다.

 

visited로 간 곳을 확인하려고 했지만, 의미없는 일이었다.

가장 처음에는 (graph[nx][ny] not in alphabet) and (visited[nx][ny] == 0)으로 작성했다.

하지만 생각해보니 set()만 확인해주면 되는 일이었다.

가보지 않은 곳일 경우, 중복한 값이라면 어차피 못 가고, 중복되지 않다면 간다.

다시 말해 결정 사항은 중복 여부에 따라서 정해진다는 것이다.

 

그리고 마지막으로 dxy에 대해서 고민했다.

전에 백준 보물섬 문제를 풀 때 겪었던 상황이었다.

PyPy3로 제출하면 AC를 받는데, Python3로 제출하면 TLE가 뜨는 상황이었다.

무엇이 문제일까 생각하던 중 list 접근은 O(n)이니까 dx, dy 접근에서 시간이 쌓이나?하는 의문이 들었다.

이와 비슷하게 백준 마인크래프트 문제를 풀 때 if-else가 아닌 if-if를 쓴 것 때문에 TLE가 난 적이 있었다.

그래서 dx, dy를 각각 방향값을 넣어 index로 찾지 않고, 튜플로 선언하여 직접 값을 받았다.

 └ dx = [-1, 1, 0, 0], dy = [0, 0, -1, 0]이 아니라 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]로 사용했다.

그렇게 Python3로 제출하니 TLE가 안 나고 성공적으로 문제를 풀었던 적이 있다.

따라서 dx, dy가 아닌 dxy로 직접 값을 받아서 사용했다.

 

여러 방면으로 시간 초과를 고려하여 작성했음에도 피할 수 없었다.

혹시나 하는 마음에 PyPy3로 제출해보았다.

 

이런... PyPy3는 통과한다...

우선 구조는 맞았다는 이야기다. 그래도 한시름 놓았다. 틀린 코드를 짠 게 아니구나.

 

if max_move == 26:
    return

백준 테트로미노 문제를 풀 때 겪었던 상황이었다.

이와 유사하지만 더 어려운 백트래킹 문제였는데, 자꾸 TLE가 떴다.

그래서 생각을 해보다가 종료 조건문을 넣어주었던 적이 있다.

이번 문제에서도 이런 종료 조건을 적용할 수 있을 것 같았다.

 

알파벳 중복을 피해서 간다면 갈 수 있는 최대 경로는 26이다.

그래서 max_move가 26이라면 더 탐색을 할 필요가 없다.

 

그랬더니 1%도 올라가지 않던 채점 현황이 1%나 올라갔다!

1조에서 1%면 무려 100억이다. 기업 입장에서는 크다. 그래 조금씩 맞춰가면 된다.

한 번 바꿀 때마다 1%면 100번만 하면 되지 않은가.

 

if max_move == 26 or (row * col) - cur_move <= max_move:
    return

26이 아니라 한 가지 조건을 더 넣어주었다.

남아있는 칸((row * col) - cur_move)이 max_move보다 작다면 굳이 더 이동할 필요가 없다.

그러니까, 남아있는 칸을 전부 탐색해도 max_move보다 작으면 탐색의 의미가 없다는 말이다.

그런 생각으로 위의 식을 작성해주었다.

 

6% 채점까지 더 늘어났다. 더 생각해보자.

 

if (row * col) - cur_move <= max_move or max_move == 26:
    return

생각해보면 26이 되는 경우보다, 가지 못하게 되는 경우가 더 많지 않을까?

이런 생각으로 위의 두 조건식의 순서를 바꿔주었다. 

 

지금 작성하면서 드는 생각이지만, 애초에 저 조건식을 잘못 짰다.

우연히 저 경우에 맞아떨어지면서, 마치 저 식이 맞은 듯한 상황이 된 것이다.

채점할 때도 %가 올라가서 맞나...? 싶었는데 아니다.

 

어쨌든 8%로 더 높아지긴 했지만, 조금 사고를 바꿀 필요가 있다. 애초에 식도 틀렸고 말이다.

너무 작은 거에 얽매이고 있다. 큰 틀에서 바라봐보자.

현재 DFS를 이용한 백트래킹으로 코드를 구현했고, TLE가 뜬다.

DFS와 백트래킹, 그리고 TLE.

어라? 그럼 비재귀 DFS로 짜면 되지 않나?

 

alphabet = set([(x, y, graph[0][0])])

생각해보면 갈 수 있는 최대 경우의 수는 26이다.

모든 경로를 저장한다고 가정했을 때, 문자열 26개, 좌표를 나타내는 숫자 2개.

그리고 이런 저장 공간이 26개 있다고 할 때, 계산해보면 1MB도 사용하지 않는다.

정확하게는 680B를 사용한다.

 └ Python3에서 list는 기본 56B, 3개의 주소 공간을 할당하는데 각 8B해서 80B다. 80 * 26 = 680

문제 조건의 256MB가 차고 넘칠 정도로 많이 남는다.

 

# ---------- Function ----------
def NonRecursiveDFS(x, y):
    global max_move
    
    alphabet = set([(x, y, graph[0][0])])

    while alphabet and max_move < 26:
        x, y, footprint = alphabet.pop()
        
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            
            if 0 <= nx < row and 0 <= ny < col and graph[nx][ny] not in footprint:
                alphabet.add((nx, ny, footprint + graph[nx][ny]))
                max_move = max(max_move, len(footprint)+1)

그리고 백트래킹으로 값을 넣고 뺀다면, 가장 첫 혹은 마지막 값에만 접근한다.

즉 0번째 값 아니면 -1번째 값이다. 이건 list로 탐색해도 무조건 O(1)이다.

 

그래서 alphabet에 좌표와 여태껏 이동한 발자취(footprint)를 저장한다.

alphabet이 빌 때까지 계속 돌고, 혹은 max_move가 26이 되는 순간 종료한다.

4방위를 탐색하면서 범위 내에 있고, footprint에 그 값이 없다면,

alphabet에 nx, ny 좌표와 현재 footprint에 graph[nx][ny]를 이은 값을 저장한다.

그리고 max_move를 업데이트한다.

 

종료 조건문은 따로 작성해주지 않아도 상관없다.

조건에 맞는 모든 구역을 다 돌면 종료하거나(while alphabet), 조기 종료(max_move < 26)한다.

 

그렇게 맞았다. 문제 풀이에 걸린 시간은 대략 45분 정도 걸렸다.

문제 해결 능력은 올라간다는 느낌이 들기는 하는데 아직도 부족하다.

문제를 잘 푼다는 게 기초가 충분하다는 사실과는 별개니까.

또한, '잘' 푼다지 '빨리' 푼다는 아니다. 코딩 테스트에서는 여유 시간을 생각해서 30분에는 끝내야 한다.

타이머를 맞춰두고 푸는 연습을 조금 더 해야 겠다.

상황에 더 몰입해야 한다.