[백준/BOJ] 1987. 알파벳 - python

문지은·2023년 3월 21일

algorithm boj

Baekjoon Online Judge

목록 보기

1/6

문제 링크 : https://www.acmicpc.net/problem/1987

🔍 문제 요약

대문자 알파벳으로 이루어진 R x C 배열이 주어진다.
말은 좌측 상단에서 시작하여 상하좌우로 이동한다.
새로 이동한 칸에 적혀있는 알파벳은 지금까지 모든 칸에 적혀있는 알파벳과는 달라야 한다.
말은 최대한 몇 칸을 지나갈수 있는지 출력하라.

📍 접근 방법

일반적인 DFS/BFS 문제이며 시간초과로 매우 고생했던 문제이다.
총 3가지 방법을 이용하여 풀이해보았다. (Main은 3번 풀이입니다)
1. DFS - path 배열 이용 : python3, pypy 모두 시간 초과
2. DFS - 알파벳 아스키코드를 이용한 DAT 배열 이용 : python3 시간초과, pypy 정답
3. BFS - python3, pypy 모두 정답

접근방법 1 - DFS (1)

방향 배열을 사용하여 좌측 상단부터 내가 갈 수 있는 곳 DFS 탐색
알파벳 중복 체크 위해 지나온 알파벳을 path 배열에 담고 중복 확인
python, pypy 모두 시간초과 발생

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

# 방향 배열 
direct_y = [-1, 1, 0, 0]
direct_x = [0, 0, -1, 1]
ans = 0
cnt = 1
def dfs(y, x):
    global ans, cnt
    ans = max(ans, cnt)
    for i in range(4):  # 상하좌우 탐색
        dy = y + direct_y[i]
        dx = x + direct_x[i]
        if 0 <= dy < R and 0 <= dx < C:  # 범위 확인
            if arr[dy][dx] not in path:  # 간 적 없는 알파벳이면
                path.append(arr[dy][dx])  # path에 담고
                cnt += 1  # count + 1
                dfs(dy, dx)
                cnt -= 1  # 리턴시 count -1, path에서도 제거
                path.remove(arr[dy][dx])

# 좌측 상단에서 시작
path = [arr[0][0]]
dfs(0, 0)
print(ans)

접근방법 2 - DFS(2)

방향 배열을 사용하여 좌측 상단부터 내가 갈 수 있는 곳 DFS 탐색
DAT 배열([0]*128)을 만들고 알파벳 아스키코드를 이용하여 방문 체크한 뒤 중복 체크
첫번째 풀이에서는 리턴시 카운트를 직접 빼주었는데, 이번에는 cnt를 매개변수로 사용하여 그 번거로움을 없앴다.
python 시간초과, pypy 정답
- 아스키코드를 이용하여 알파벳 대문자를 십진수로 바꾸면 65~90, 소문자를 십진수로 바꾸면 91~122이라 DAT 배열 크기를 넉넉하게 128개로 하였는데, 문제에서 주어진 조건이 알파벳 대문자라고 했기 때문에 26개만 만들었으면 시간을 좀 더 줄일 수 있었을 것 같다.

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

direct_y = [-1, 1, 0, 0]
direct_x = [0, 0, -1, 1]

def dfs(ci, cj, cnt):
    global ans
    ans = max(ans, cnt)
    for i in range(4):  # 상하좌우 탐색
        dy = ci + direct_y[i]
        dx = cj + direct_x[i]
        if 0 <= dy < R and 0 <= dx < C:  # 범위 체크 
            if visited[ord(arr[dy][dx])] == 0:  # 알파벳 중복 체크
                visited[ord(arr[dy][dx])] = 1
                dfs(dy, dx, cnt+1)
                visited[ord(arr[dy][dx])] = 0  # 리턴시 중복체크 해제

ans = 1
visited = [0]*128
visited[ord(arr[0][0])] = 1
dfs(0, 0, 1)
print(ans)

접근방법 3 - BFS

끝까지 확인하고 리턴하는 DFS와 달리 BFS는 뻗어 나가는 것이기 때문에 알파벳 중복 체크를 할때 단순히 같은 알파벳만 사용했는지만 확인해서는 안된다.
예를 들어, 아래 예시에서 좌측 상단 부터 H-A-J-F 순서로 움직인 것과, H-F-J-A로 움직인 것은 사용한 알파벳은 같지만 다음 경로가 완전히 달라질 수 있다!

따라서, 어떤 경로로 거쳐서 왔는지 시퀀스(순서)확인도 필요하다.

코드 설계

알파벳 중복 확인

q를 deque로 선언(리스트로 선언하는 것보다 빠름)
현재 y좌표, x좌표, 시퀀스(ci, cj, cv)를 q에 담아서 확인
시퀀스는 string으로 생성
다음에 올 좌표의 알파벳 arr[ni][nj] 이 현재 내 시퀀스 안에 담겨 있으면 안됨 not in cv

중복 시퀀스 확인

arr과 같은 크기의 비어있는 2차원 배열(v)생성
좌표를 방문할 때 어떤 경로를 거쳐서 왔는지 v배열 해당 좌표에 시퀀스 삽입
다음에 이동할 시퀀스cv+arr[ni][nj]가 가본 적 없는 경로여야 함(v배열의 다음 이동할 좌표에 존재하는 시퀀스이면 안됨)not in v[ni][nj]
in 연산자를 사용할 때 list 자료형(O(n)) 보다 set 자료형(O(1))이 더 빠르므로 v 배열을 set 자료형으로 생성
시퀀스(cv)의 길이가 이동한 칸 수 -> 최소값 출력 !

from collections import deque

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

def bfs():
    q = deque()
    # list는 O(N), set은 O(1)
    v = [[set() for _ in range(C)] for _ in range(R)]
    ans = 1

    # q에 초기 데이터 삽입
    q.append((0, 0, arr[0][0]))
    v[0][0].add(arr[0][0])

    while q:
        ci, cj, cv = q.popleft()  # y좌표, x좌표, 시퀀스
        ans = max(ans, len(cv))
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ni, nj = ci+di, cj+dj
            # 범위 확인
            if 0 <= ni < R and 0 <= nj < C:
                # 알파벳이 중복되지 않아야 함
                if arr[ni][nj] not in cv:
                    # 시퀀스가 중복되지 않아야 함
                    if cv + arr[ni][nj] not in v[ni][nj]:
                        q.append((ni, nj, cv+arr[ni][nj]))
                        v[ni][nj].add((cv+arr[ni][nj]))
    return ans

print(bfs())