Python-1987-알파벳

알파벳 click

 

풀릴것 같으면서도 메모리 초과와 시간초과에 시달렸던 문제였다.

BFS를 하면서 set자료구조를 사용할 생각을 한 번도 해본적이 없었는데, 이 문제에서 처음으로 set을 사용해서 풀었다.

 

탐색을 하면서 중복을 제거해 주는 부분이 정말 중요했다.

 

 

문제 분석

 

문제에 명시되어 있듯이, 새로 이동하는 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 하지만, 이 조건만 적용해 dfs를 수행하면 시간초과가 발생하게 된다.

 

Code - 시간초과 발생

import sys
from collections import deque
read=sys.stdin.readline

n,m = map(int,read().split())
board = list(list(read().strip()) for _ in range(n))
visited = list(1 for _ in range(ord('Z')+1))

answer = 0

def dfs(a,b,cnt):
    answer = cnt
    visited[ord(board[a][b])] = 0
    
    for x,y in ((1,0), (0,1), (0,-1), (-1,0)):
        ax, by = a+x, b+y
        if 0<=ax<n and 0<=by<m and visited[ord(board[ax][by])]:
            answer = max(answer , dfs(ax,by,cnt + 1))
    visited[ord(board[a][b])] = 1
    return answer

print(dfs(0,0,1))

 

 

중복 제거

 

경로 내에 속해 있는 알파벳 뿐만 아니라, 동일한 좌표이며, 지나온 알파벳 순서도 동일한 경우들을 제외시켜주어야 한다.

 

deque 대신 set에 추가해 좌표와 방문한 점이 같은 점들의 중복을 제거

문제의 입력 예시를 살펴보자.

0,0 부터 1,1까지 도달하는 경로는 'CAD'와 'CAD'가 존재한다. 다른 경로이지만, 지나온 알파벳 순서들이 동일하다.

이런 경우들에 대해 중복을 제거해 주어야 한다.

(1,1) 까지 동일한 알파벳을 거쳐온 경우, 앞으로 지날 수 있는 경로의 수도 동일하다. 이들의 중복을 제거하지 않고 각각의 경우에 대해 모두 탐색하는 것이 시간초과의 원인이었다.

 

set자료구조에 좌표와 경로를 넣어줌으로써 위의 경우에 대한 중복을 제거할 수 있다.

 

**set자료구조는 순서를 보장하지 않는다. 하지만, 우리가 set에 추가하는 값에는 좌표, 경로, 지나온 알파벳의 개수 정보들이 모두 들어있다. 따라서, 순서에 상관없이 뽑아서 진행해도 지나온 알파벳의 최대 개수를 찾는데는 문제가 없다!

 

    point = set()

    point.add((0,0,board[0][0]))
    while point:
        a,b, way = point.pop()
        cnt = max(cnt, len(way))
        for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
            ax,by = a+x,b+y
            if 0<=ax<n and 0<=by<m and board[ax][by] not in way:
                point.add((ax,by,way+board[ax][by]))

BFS를 수행하는데 set을 쓴다는 것이 굉장히 어색했지만, 이런 방법이 있다는 것도 알 수 있었던 경험이었다.

BFS는 무조건 deque라는 편견을 깨자! (사실, 코드가 BFS의 형태를 띄고 있지만, 추가한 정보들을 순서에 상관없이 뽑기 때문에 BFS라고 할 수 있는지는 모르겠다.)

 

 

 

Code

import sys
from collections import deque
read=sys.stdin.readline

n,m = map(int,read().split())
board = list(list(read().strip()) for _ in range(n))

def BFS():
    cnt = 0
    point = set()
    point.add((0,0,board[0][0]))
    while point:
        a,b, way = point.pop()
        cnt = max(cnt, len(way))
        for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
            ax,by = a+x,b+y
            if 0<=ax<n and 0<=by<m and board[ax][by] not in way:
                point.add((ax,by,way+board[ax][by]))
    return cnt

print(BFS())

 

 

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]