[BOJ] 1987 - 알파벳

김우경·2020년 12월 19일

알고리즘

목록 보기

26/69

문제 링크

문제 설명

가로 R* 세로 C 크기의 보드 각 칸에 알파벳이 적혀있다. 좌측 상단 (0,0)에서부터 말이 이동하는데, 이때 상하좌우 한칸 중 그동안 지나지 않은 알파벳이 적힌 칸에만 이동할 수 있다. 말이 최대 몇칸까지 이동할 수 있는지 구하시오

문제 풀이

해당 칸까지 도달하는데 지나친 칸들, 즉 path를 기억해야 한다는 부분에서 DFS가 더 쉬울것 같아서 DFS로 풀려고 했다.

시도 1 (DFS)

import sys

input = sys.stdin.readline

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

def in_bound(x, y):
    if x in range(0, R) and y in range(0, C):
        return True
    else:
        return False

def dfs(x, y, count):
    global answer
    answer = max(answer, count)
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_bound(nx, ny):
            if path[ord(Map[nx][ny]) - 65] != 1:
                path[ord(Map[nx][ny]) - 65] = 1
                dfs(nx, ny, count+1)
                path[ord(Map[nx][ny]) - 65] = 0

R, C = map(int, input().split())
Map = []

for _ in range(R):
    Map.append(list(input().strip()))

answer = 1
path = [0]*26
path[ord(Map[0][0]) - 65] = 1
dfs(0, 0, answer)
print(answer)

코드는 간단한데 계속 시간초과가 나서 틀린 부분 찾는데 애먹었음^_ㅠ,,

지나쳐온 path를 path 리스트에 직접 해당 알파벳을 append하고, not in을 이용하여 알파벳을 지나쳤는지 검사했다. 시간초과가 나서 path를 흔히 사용하는 visited 리스트와 같은 개념으로 해당 알파벳을 방문했는지에 대해 체크를 했는데, 이 부분만 변경하니까 pypy3으로 통과됨 ,,
근데 구글링 하다 발견한 이 테케

20 20
ZYXWVUTSRQPONMLKJIHG
YXWVUTSRQPONMLKJIHGF
XWVUTSRQPONMLKJIHGFE
WVUTSRQPONMLKJIHGFED
VUTSRQPONMLKJIHGFEDC
UTSRQPONMLKJIHGFEDCB
TSRQPONMLKJIHGFEDCBA
SRQPONMLKJIHGFEDCBAA
RQPONMLKJIHGFEDCBAAA
QPONMLKJIHGFEDCBAAAA
PONMLKJIHGFEDCBAAAAA
ONMLKJIHGFEDCBAAAAAA
NMLKJIHGFEDCBAAAAAAA
MLKJIHGFEDCBAAAAAAAA
LKJIHGFEDCBAAAAAAAAA
KJIHGFEDCBAAAAAAAAAA
JIHGFEDCBAAAAAAAAAAA
IHGFEDCBAAAAAAAAAAAA
HGFEDCBAAAAAAAAAAAAA
GFEDCBAAAAAAAAAAAAAA

는 통과하지 못한다 왜지 >????

풀이를 찾아보니까 다들 BFS로 풀었길래 BFS로도 다시 풀어봤다.

시도 2 (BFS)

import sys
from collections import deque

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
R, C = map(int, input().split())
Map = []

for _ in range(R):
    Map.append(list(input().strip()))

answer = 1

def in_bound(x, y):
    if x in range(0, R) and y in range(0, C):
        return True
    else:
        return False

def bfs(x,y):
    global answer
    queue = set([(x,y, Map[x][y])])
    
    while queue:
        #print(queue)
        x, y, path = queue.pop()

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx, ny):
                if Map[nx][ny] not in path:
                    queue.add((nx, ny, path+Map[nx][ny]))
                    answer = max(answer, len(path)+1)

bfs(0,0)
print(answer)