손가락놀이터

문제 후기

1. 문제를 보고 DFS나 BFS로 풀어야되는 것을 파악했다. 먼저 DFS로 풀어봤다.
2. 처음에 DFS로 풀면서 set을 활용해서 했다. 칸을 넘어갈때마다 set에 add, remove를 하면서 하니 시간초과가 발생했다. -> 그래서 메모이제이션으로 각 알파벳의 활용 여부를 1, 0으로 나타내야했다.
3. BFS로 풀어볼때는 deque를 활용해서 풀려고 했다. deque를 활용하니 이번에는 메모리초과....... 확인해보니 2가지 경우가 동시에 같은 칸으로 가는 경우가 있고 알파벳 역시 동일한 경우였다. 혼자 해결을 하지 못해 찾아보니 deque가 아닌 set을 활용....😥 BFS를 할 때 항상 deque만 활용하던 것이 잘못된 것이었다. 다음부터는 확실하게 이해하고 어떤 것을 써야할지 생각하자.

문제링크

from sys import stdin
from _collections import deque

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

# dfs로 풀 경우 메모이제이션으로 각 알파벳 visit 체크해야함.
def dfs(y, x, ans):
    global answer, chk

    answer = max(ans, answer)

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < R and 0 <= nx < C:
            # print(ny, nx, matrix[ny][nx], chk)
            if matrix[ny][nx] not in chk:
                chk.add(matrix[ny][nx])
                dfs(ny, nx, ans+1)
                chk.remove(matrix[ny][nx])

# bfs로 풀 경우 deque로 할 경우 중복되는 경우 때문에 메모리 초과 발생. set으로 해결해야함.
def bfs(y, x, chk):

    answer = 1
    queue = set([(y, x, chk)])

    while queue:
        ay, ax, chk_val = queue.pop()
        answer = max(answer, len(chk_val))

        for i in range(4):
            ny, nx = ay + dy[i], ax + dx[i]
            if 0 <= ny < R and 0 <= nx < C and matrix[ny][nx] not in chk_val:
                queue.add((ny, nx, chk_val + matrix[ny][nx]))
    
    return answer

R, C = map(int, stdin.readline().split())

matrix = [list(map(str, input())) for _ in range(R)]
chk = matrix[0][0]

print(bfs(0,0,chk))