[백준_1987] 알파벳(bfs, set, bactracking)

[백준_1987] 알파벳(bfs, set, bactracking)

 

고생한 문제다.....

처음에 dfs로 시도했다가 시간 초과가 떴다.

 

첫 풀이 passed는 지나간 알파벳을 문자열로 저장했고

visited는 전체 행렬에 trace를 알 수 있도록 했었다.

둘 다 시간초과

 

import sys
input = sys.stdin.readline

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def bt(x,y,lengg):
    global leng
    leng = max(leng, lengg)

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if arr[nx][ny] not in passed:
                passed.append(arr[nx][ny])
                bt(nx,ny, lengg+1)
                passed.remove(arr[nx][ny])

leng = 0
n, m = map(int, input().split())

arr = [list(input().strip()) for _ in range(n)]
passed = [arr[0][0]]

bt(0,0,1)
print(leng)

import sys
input = sys.stdin.readline

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def bt(x,y,lengg):
    global leng
    leng = max(leng, lengg)

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if arr[nx][ny] not in visited[x][y]:
                visited[nx][ny] = visited[x][y] + arr[nx][ny]
                bt(nx,ny, lengg+1)
                visited[nx][ny] = ''

leng = 0
n, m = map(int, input().split())

arr = [list(input().strip()) for _ in range(n)]
visited = [[""] * (m+1) for _ in range(n)]
visited[0][0] += arr[0][0]

bt(0,0,1)
print(leng)

 

 

결국

set을 이용하여 해당 문자열이 있는지 찾는 것, 넣고 빼고 부분의 연산 속도를 향상해야했다.

내 생각에 이 코드에서 핵심적인 부분은 set을 이용해 찾는 속도를 올린부분 + 지나온 알파벳을 기록하는 paased에 remove가 필요없이 구현되었다는 점이다.

이것은 bfs 함수 인자에 passed를 함께 넣어서 가능했던 부분이다.

즉 queue = set()에서 pop()과 add 만으로 구현하여 시간이 훨씬 줄 수 있었다. !

 

import sys
input = sys.stdin.readline

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def bfs(p,q):
    global mmax
    cnt = 1

    queue = set()
    queue.add((p,q,cnt, arr[0][0]))
    while queue:
        x, y, cnt, passed = queue.pop()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if arr[nx][ny] not in passed:
                    queue.add((nx,ny, cnt+1,passed + arr[nx][ny]))
                    mmax = max(mmax, cnt+1)
                    print(queue)
    print(mmax)

mmax = 1
n, m = map(int, input().split())

arr = [list(input().strip()) for _ in range(n)]

bfs(0,0)

 

 

이 문제에서 배운 부분은

백트래킹시

bfs의 경우 remove 대신 visited를 queue에 같이 넣고 빼주면 되고

dfs의 경우 remove를 직접 명시적으로 구현해야하는 점이다.