문제 링크

문제 소개

해당 문제는 어떠한 배열판에서 알파벳을 (0,0)부터 시작해서 동서남북으로 가되 전에 선택한 알파벳이 중복이 안되도록 건널때 최대로 이동할 수 있는 알파벳 수를 물어보는 문제이다.

우선 문제를 처음 봤을 때 DFS로 풀면 될 것 같았다.

그럼으로 아래의 코드처럼 어렵지 않게 코드를 작성하였다.

import sys


def move(board, y, x, visited, cnt):
    global ans
    for i in range(4):
        ny, nx = y + controlY[i], x + controlX[i]
        if -1 < ny < R and -1 < nx < C and not visited[board[ny][nx]]:
            visited[board[ny][nx]] = True
            move(board, ny, nx, visited, cnt + 1)
            visited[board[ny][nx]] = False
    if ans < cnt:
        ans = cnt


def solution():
    global R, C, controlY, controlX, ans
    input = sys.stdin.readline
    R, C = map(int, input().split())
    board = [list(input().rstrip('\n')) for _ in range(R)]

    controlY, controlX = [0, 0, 1, -1], [1, -1, 0, 0]
    visited = {chr(x): False for x in range(65, 91)}
    visited[board[0][0]] = True
    ans = 1
    move(board, 0, 0, visited, 1)
    print(ans)


solution()

하지만, 위의 코드를 실제로 돌려보면 시간초과가 발생한다.

내가 생각한 시간초과 발생 이유는 아래와 같다.

1. visited에서 dictionary로 선언하여 key를 문자열로 지정
2. 알파벳은 최대 26개임으로, 만약 ans가 26개가 됬을 때도 종료하지 않음

이러한 부분을 수정해서 아래와 같이 코딩하였다.

import sys


def dfs(board, y, x, visited, cnt):
    global ans
    if ans < cnt:
        ans = cnt
    for i in range(4):
        ny, nx = y + controlY[i], x + controlX[i]
        if -1 < ny < R and -1 < nx < C and not visited[board[ny][nx]]:
            visited[board[ny][nx]] = True
            dfs(board, ny, nx, visited, cnt + 1)
            visited[board[ny][nx]] = False


def solution():
    global R, C, controlY, controlX, ans
    input = sys.stdin.readline
    R, C = map(int, input().split())
    board = [list(map(lambda x:ord(x) - 65,input().rstrip('\n'))) for _ in range(R)]
    controlY, controlX = [0, 0, 1, -1], [1, -1, 0, 0]
    visited = [0 for _ in range(26)]
    visited[board[0][0]] = True
    ans = 1
    dfs(board, 0, 0, visited, 1)
    print(ans)


solution()

하지만 이러한 방식은 pypy에서만 정답처리되었고, 심지어 시간도 처참했다(6256ms).

그럼으로 다른 방식으로 풀어보고자 하였다.

해결책 (BFS)

여러가지 해결책이 있지만, 단순명료한 것은 BFS가 아닐까싶다.

하지만 아래의 부분을 통해 커스텀하게 BFS를 사용하여 해결하였다.

해결 팁
1. deque 사용시 시간 초과 -> set으로 바꿈
2. footprint를 남겨서 다음 칸으로 넘어갈 때, 중복되는 부분 최소화

import sys


def bfs(board):
    controlY, controlX = [0, 0, 1, -1], [1, -1, 0, 0]
    needVistied = set([(0, 0, board[0][0])])
    ans = 0
    while needVistied:
        y, x, visited = needVistied.pop()
        flag = True
        for i in range(4):
            ny, nx = y + controlY[i], x + controlX[i]
            if -1 < ny < R and -1 < nx < C and board[ny][nx] not in visited:
                flag = False
                needVistied.add((ny, nx, visited + board[ny][nx]))
        if flag:
            ans = max(ans, len(visited))
    print(ans)


def solution2():
    global R, C
    input = sys.stdin.readline
    R, C = map(int, input().split())
    board = [list(input().rstrip('\n')) for _ in range(R)]
    bfs(board)


solution2()

위의 코드는 위의 해결 팁 1번(deque 사용시 시간 초과 -> set으로 바꿈)만 적용한 코드이다.

이 부분을 통해 시간을 1364ms까지 줄였다.

최종 코드

import sys

def bfs(board):
    controlY, controlX = [0, 0, 1, -1], [1, -1, 0, 0]
    needVistied = [(0, 0, board[0][0])]
    check = [['' for _ in range(C)] for _ in range(R)]
    ans = 1
    while needVistied:
        y, x, visited = needVistied.pop()
        for i in range(4):
            ny, nx = y + controlY[i], x + controlX[i]
            if -1 < ny < R and -1 < nx < C and board[ny][nx] not in visited:
                tmp = visited + board[ny][nx]
                if check[ny][nx] != tmp:
                    check[ny][nx] = tmp
                    needVistied.append((ny, nx, visited + board[ny][nx]))
                ans = max(ans, len(tmp))
        if ans == 26:
            break

    print(ans)


def solution2():
    global R, C
    input = sys.stdin.readline
    R, C = map(int, input().split())
    board = [list(input().rstrip('\n')) for _ in range(R)]
    bfs(board)


solution2()

위의 코드는 코드 팁 1번과 2번을 적용해서 문제를 해결하여 기존의 6256ms를 564ms로 업그레이드 시켰다.