📚 1987 - 알파벳

알파벳

이해

문제를 보자마자, 쉽구나 라는 생각에 바로, dfs를 이용하여 제출하였다.

❌ 사용했던 것
딕셔너리 라이브러리를 사용해서 방문했는지 체크했다.

결과... 시간 초과

이해가 안되서 질문들을 보니, 나와 같은 사람이 많다는 것을 알게 되었다.
검색을 해보니, 알파벳 크기는 정해져 있으니

• dfs를 사용할 때는 알파벳 크기의 배열을 만들어, 방문했다면 체크하고, 하지 않았을 경우 체크를 해지 한다.
• bfs를 사용할 때는 입력 배열 크기의 check 이차원 배열을 만들어, 거리로 계산을 한다. 위치를 기준으로 저장된 데이터가 같을 경우 pass, 아니면 알파벳 삽입

➡️ bfs가 dfs 보다 시간 복잡도 및 효율적이다!

소스

dfs

import sys

sys.setrecursionlimit(2 ** 8)

read = sys.stdin.readline

r, c = map(int, read().split())

board_card = []

for _ in range(r):
    board_card.append(list(map(str, read().strip())))

result = 0
check = [False] * 26

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


def dfs(x, y, cnt):
    # print("현재 x, y", x, y, cnt)
    # print("방문 한 곳 : ", visited)
    global result
    result = max(result, cnt)

    for i in range(4):
        next_x = dx[i] + x
        next_y = dy[i] + y

        if 0 <= next_x < r and 0 <= next_y < c:
            check_idx = ord(board_card[next_x][next_y]) - 65
            if not check[check_idx]:
                check[check_idx] = True
                dfs(next_x, next_y, cnt + 1)
                check[check_idx] = False


check[ord(board_card[0][0]) - 65] = True
dfs(0, 0, 1)

print(result)

bfs

import sys

read = sys.stdin.readline
R, C = map(int, read().split())
graph = [read().strip() for _ in range(R)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def bfs(a, b):
    q = {(a, b, graph[a][b])}
    check = [['' for _ in range(C)] for _ in range(R)]
    check[a][b] = graph[a][b]
    result = 1
    while q:
        x, y, track = q.pop()
        result = max(result, len(track))
        if result == 26:
            break
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 좌표 nx, ny을 기준으로 (현재 위치에 저장되어 있는 결과 와 이전 결과 + graph 현재 위치) 가 다르다면
            # check nx, ny에 결과를 저장한다.
            if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] not in track and check[nx][ny] != track + graph[nx][ny]:
                check[nx][ny] = track + graph[nx][ny]
                q.add((nx, ny, check[nx][ny]))
    return result


print(bfs(0, 0))