[백준/파이썬] 1987: 알파벳

백준으로 문제 보러 가기~

인트로(TMI)

저번 주부터 회사에 다니기 시작했다! 나는 주로 React를 다뤘는데, 회사에서는 Vue를 사용한다.. 그래서 Vue 공부를 하느라고 문제를 별로 못 풀었다 ㅠㅠㅠ 그러다 푸니까 넘 재밌었다!!!!
쉬운 줄 알았는데 시간 초과가 많이 나서 신경을 썼다...재밌는 DFS문제였다!!

풀이

세로 R칸, 가로 C칸 표 모양의 보드에 대문자 알파벳이 써있다.
좌측 상단에서 시작해서, 상하좌우 4칸 중 한 칸으로 갈 수 있다. 매번 다른 알파벳을 지나면서, 가장 많이 이동하는 칸 수를 구하는 문제였다!!
이동하는 모든 경우를 고려해야 하고 R, C 가 20 이하여서.. DFS로 풀 수 있을 거라고 생각했다.

처음에는 방문했던 알파벳인지 체크하는 것을 set으로 했는데, 시간 초과가 나왔다 ㅠㅠ

import sys

input = sys.stdin.readline
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

R, C = map(int, input().split())
board = list(input().strip() for _ in range(R))

ans = 0

visited = [[False] * C for _ in range(R)]


def dfs(i, j):
    global ans
    visited[i][j] = True
    for k in range(4):
        ni, nj = i + directions[k][0], j + directions[k][1]
        if 0 <= ni < R and 0 <= nj < C and not visited[ni][nj]:  # 범위, 방문 체크
            if board[ni][nj] not in history:  # 알파벳이 안 겹치면
                history.add(board[ni][nj])
                visited[ni][nj] = True
                dfs(ni, nj)
                if board[ni][nj] in history:
                    history.remove(board[ni][nj])
                visited[ni][nj] = False
            else:
                ans = max(ans, len(history))


history = set()
history.add(board[0][0])
dfs(0, 0)

print(ans)

고민하다가 게시판을 봤는데 리스트로 만들어서 체크를 해보라는 걸 봤다.!
알파벳 그것도 대문자만 나오니까 리스트를 26으로 만들어서 체크를 하면, 방문 체크도 할 필요 없고! O(1)으로 방문했던 알파벳인지 체크할 수 있다! (근데 set에서 in도 O(1) 인데...??)

그래서 history를 set에서 방문한 알파벳 체크하는 리스트로 바꿔서 사용했다!

import sys

input = sys.stdin.readline
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

R, C = map(int, input().split())
board = list(input().strip() for _ in range(R))

ans = 0

def dfs(i, j):
    global ans
    ans = max(ans, sum(history))
    for k in range(4):
        ni, nj = i + directions[k][0], j + directions[k][1]
        if 0 <= ni < R and 0 <= nj < C and history[ord(board[ni][nj])-65] == False:  # 범위  체크, 알파벳 겹치나
            tmp = ord(board[ni][nj])-65
            history[tmp] = True
            dfs(ni, nj)
            history[tmp] = False

history = [False]*26
history[ord(board[0][0])-65] = True
dfs(0, 0)

print(ans)

로 해도 시간 초과가 났다..ㅠㅠ

아래와 같이 고치니 드디어 성공!!

• sum(history) 할 때 sum이 시간이 좀 걸리는 것 같다. 그래서 방문한 알파벳 수를 세기 위해서 dfs 함수의 인자로 cnt를 추가했다.

import sys

input = sys.stdin.readline
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

R, C = map(int, input().split())
board = list(input().strip() for _ in range(R))

ans = 0

def dfs(i, j,cnt):
    global ans
    for k in range(4):
        ni, nj = i + directions[k][0], j + directions[k][1]
        if 0 <= ni < R and 0 <= nj < C and history[ord(board[ni][nj])-65] == False:  # 범위  체크, 알파벳 겹치나
            tmp = ord(board[ni][nj])-65
            history[tmp] = True
            dfs(ni, nj,cnt+1)
            history[tmp] = False

        else:
            ans = max(ans, cnt)


history = [False]*26
history[ord(board[0][0])-65] = True
dfs(0, 0,1)

print(ans)