난이도

Gold 4

풀이 참고 유무

?

막힌 부분

메모리, 시간 초과

문제

문제 바로가기

입력

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

출력

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

예제 입력

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력

6

문제 검토

일단 보기에는 DFS를 풀 때 시간복잡도가 안 복잡해 보이고 조건도 어려워보이지 않는다.

풀이(python)

Python - set

import sys
input=sys.stdin.readline
row,col=map(int,input().split())
matrix=[input().strip() for _ in range(row)]
visited=[[0 for _ in range(col)] for _ in range(row)]
answer=[]
def dfs(r,c,depth,alpha):
    alpha=set(alpha)
    global answer
    if r<0 or r>=row or c<0 or c>=col:
        answer.append(depth)
        return
    if visited[r][c]==1:
        answer.append(depth)
        return
    if matrix[r][c] in alpha:
        answer.append(depth)
        return
    visited[r][c]==1
    alpha.add(matrix[r][c])
    alpha=list(alpha)
    dfs(r-1,c,depth+1,alpha[:])
    dfs(r,c-1,depth+1,alpha[:])
    dfs(r,c+1,depth+1,alpha[:])
    dfs(r+1,c,depth+1,alpha[:])
dfs(0,0,0,set())
print(max(answer))

#아이디어
dfs는 한번 돌림 처음 들어왔을 때 범위를 넘지 않고 방문하지 않았고 in set에 해당하지 않으면 방문체크 cnt+1-> 만난 알파벳을 set에 add -> 다음 탐색 시작 -> 끝을 만나면 depth를 append

#시간 복잡도
v는 최대 400, e는 4x400, in은 list에서는 O(n)이지만 set에서는 O(1)의 수행시간을 가지고 있음 따라서 연산횟수는 2000남짓 ok

자료구조
set-알파벳을 담을 함수, answer-depth를 담을 리스트, int[][] - visited, int [][] - matrix

Python - dictionary

from collections import defaultdict
import sys
input=sys.stdin.readline
row,col=map(int,input().split())
matrix=[input().strip() for _ in range(row)]
alpha=defaultdict(int)
for x in range(97,123):
    alpha[chr(x)]
answer=[]
def dfs(r,c,depth,alphas):        
    global answer
    if r<0 or r>=row or c<0 or c>=col:
        answer.append(depth)
        return
    if alphas[matrix[r][c]]!=0:
        answer.append(depth)
        return
    alphas[matrix[r][c]]+=1
    dfs(r-1,c,depth+1,alphas.copy())
    dfs(r,c-1,depth+1,alphas.copy())
    dfs(r,c+1,depth+1,alphas.copy())
    dfs(r+1,c,depth+1,alphas.copy())
    
dfs(0,0,0,alpha.copy())
print(max(answer))

#아이디어
set은 a~z로만 되어 있으므로 최악복잡도랑 직접적 상관은 없고, O(1) 복잡도라고 해서 항상 빠른 건 아니고 비례상수가 클 수 있다는 걸 유념하자.
따라서 딕셔너리로 아이디어를 전환한다.
그리고 만났던 알파벳은 다시 갈 수 없기 때문에 굳이 방문처리도 필요 없다.
먼저 딕셔너리에 모든 알파벳을 초기화 -> 알파벳을 만났을 때 그 알파벳의 value가 0이 아니라면 return

#시간 복잡도
딕셔너리는 key로 찾기 때문에 O(1)이라고 볼 수 있다.abs
위에서 말한 dfs 시간에 O(1)의 오버헤드는 충분할 것으로 보인다.

자료구조
dictionary-알파벳을 담을 해쉬맵, answer-depth를 담을 리스트, int [][] - matrix

Python - list

from collections import defaultdict
import sys
input=sys.stdin.readline
row,col=map(int,input().split())
matrix=[input().strip() for _ in range(row)]
alpha=list()
for x in range(65,91):
    alpha.append(0)
answer=[]
def dfs(r,c,depth,alphas):        
    global answer
    if r<0 or r>=row or c<0 or c>=col:
        answer.append(depth)
        return
    idx=ord(matrix[r][c])-65
    if alphas[idx]!=0:
        answer.append(depth)
        return
    alphas[idx]+=1    
    
    dfs(r-1,c,depth+1,alphas[:])
    dfs(r,c-1,depth+1,alphas[:])
    dfs(r,c+1,depth+1,alphas[:])
    dfs(r+1,c,depth+1,alphas[:])
    
dfs(0,0,0,alpha[:])
print(max(answer))

#아이디어
딕셔너리는 copy함수에서 시간을 많이 소요해 시간초과가 생겼다.
그래서 위처럼 list를 사용했지만 이번에는 메모리 초과가 났다.
딕셔너리가 시간초과를 통과했어도 메모리 초과가 생겼을 것이다.
복사하는 시간이 오래걸리고 공간복잡도도 매우 크다.

Python - 백트랙킹

import sys
input=sys.stdin.readline
row,col=map(int,input().split())
matrix=[list(input().strip()) for _ in range(row)]
answer=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def dfs(r,c,depth):    
    global answer
    answer=max(answer,depth)    
    for mv in range(4):
        nr=r+dx[mv]
        nc=c+dy[mv]        
        if nr<0 or nr>=row or nc<0 or nc>=col:                        
            continue
        if matrix[nr][nc] in alpha:                        
            continue
        alpha.add(matrix[nr][nc])
        dfs(nr,nc,depth+1)
    #더 이상 갈 곳이 없어서 막혔다면 삭제
    alpha.remove(matrix[r][c])        
alpha=set()
alpha.add(matrix[0][0])
dfs(0,0,1)
print(answer)

#아이디어
dfs는 한번 돌림 처음 들어왔을 때 depth와 answer 중 큰 것을 answer에 담음 범위를 넘지 않고 방문하지 않았고 in set에 해당하지 않으면 방문체크 cnt+1-> 만난 알파벳을 set에 add -> 다음 탐색 시작 -> 끝을 만나면 스택 구조로 하나씩 리턴이 되는데 그 때 마다 사용했던 알파벳을 remove로 반납하여 약간 백트래킹의 형태로 한정된 조건으로 dfs를 진행한다.

#시간 복잡도
v는 최대 400, e는 4x400, in은 list에서는 O(n)이지만 set에서는 O(1)의 수행시간을 가지고 있음 따라서 연산횟수는 2000남짓 ok
사용했던 swt의 원소들을 다 쓰고 삭제해주기 때문에 copy하는 과정이 필요하지 않고 set을 재활용하여 수행시간을 많이 줄일 수 있었다.
결론적으로 set(O(1))로도 많은 시간을 소요했던 것은 DFS가 그만큼 많이 호출이 되었기 때문이다.
Alphabet을 set에 담으면서 한정된 조건을 생성했지만 끝을 만나게 되면 그 조건을 해제하고 또 다른 조건을 만들어가며 dfs를 수행했다.
일반 DFS라면 위 계산한 수행속도가 맞아야하지만, 조건이 계속 바뀌고 방문처리가 없는 DFS이기 때문에 백트랙킹 문제라고 할 수 있다.
백트랙킹은 일반적으로 많은 수행시간을 갖을 수 밖에 없기 때문에 나의 풀이가 시간 초과가 났다.

자료구조
set-알파벳을 담을 집합, answer-depth를 담을 리스트, int[][] - visited, int [][] - matrix

걸린 시간

22:11 (테케 통과, 시간초과 풀이 기준)

총평

얻어간 것:

1. 백트랙킹의 시간복잡도는 대부분 꽤나 복잡하다

2. set과 딕셔너리의 탐색은 O(1)이지만 너무 많은 데이터가 몰려 있으면 비례상수로 때론 많은 시간 복잡도를 소요한다. (이번 문제 해당x)

3. set의 in과 dict의 in도 O(1)의 시간을 소요하지만 위와 마찬가지다.

4. 알파벳을 딕셔너리 키로 사용할 때 공간과 list에서 아스키코드를 이용해 저장하는 방법이 있다.

5. 스택 구조에서 리턴해오면서 사용했던 조건들을 회수하고 다시 dfs를 수행하는 백트랙킹을 사용하면 공간복잡도를 많이 줄일 수 있다.