[Python] 백준 <1987-알파벳>

https://www.acmicpc.net/problem/1987

 

- BFS 풀이

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

def bfs(a, b):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    dq = deque()
    # deque에 지나온 알파벳도 같이 저장
    dq.append((a, b, [map_li[a][b]]))

    visited = set()
    visited.add((a, b, tuple([map_li[a][b]])))

    cnt = 1

    while dq:
        x, y, alpha = dq.popleft()
        cnt = max(cnt, len(alpha))

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 > nx or nx >= R or 0 > ny or ny >= C:
                continue
            # 이미 방문한 알파벳이면 pass
            if map_li[nx][ny] in alpha:
                continue

            new_alpha = alpha + [map_li[nx][ny]]  # 복사본 생성
            state = (nx, ny, tuple(new_alpha))
            if state in visited:
                continue

            visited.add(state)
            dq.append((nx, ny, new_alpha))

    return cnt

R, C = map(int, input().split())
map_li = [input().strip() for _ in range(R)]

dap = bfs(0, 0)
print(dap)

 

- DFS + 백트래킹 풀이 (시간 초과)

import sys
sys.setrecursionlimit(1_000_000)
input = sys.stdin.readline

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
dap = 1  # 시작칸 포함

def dfs(x, y, alpha):
    global dap
    # 현재까지 길이 갱신
    if len(alpha) > dap:
        dap = len(alpha)

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 > nx or nx >= R or 0 > ny or ny >= C:
            continue

        ch = map_li[nx][ny]
        if ch in alpha:
            continue

        alpha.append(ch)     # 선택
        dfs(nx, ny, alpha)   # 내려감
        alpha.pop()          # 되돌림 (백트래킹)

R, C = map(int, input().split())
map_li = [input().strip() for _ in range(R)]

dfs(0, 0, [map_li[0][0]])
print(dap)