[DFS]백준 1987번 알파벳 with Python3

https://www.acmicpc.net/problem/1987

1987번: 알파벳

문제

 

내 풀이

from collections import deque
import sys
sys.setrecursionlimit(10000)

input = sys.stdin.readline
rr, cc = map(int, input().split())

alpha = []
str1 = ''
for _ in range(rr):
    str = input().rstrip()
    # str1 = str1 + str
    alpha.append(list(str))

# str_unique = ''.join(set(str1))
# alpha_unique = list(str_unique)
# print(alpha_unique)

visited = deque([])
visit = [[0] * (cc) for _ in range(rr)]

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
count = 0


def dfs(r, c):
    global count
    visited.append(alpha[r][c])
    visit[r][c] = 1

    for m in range(4):
        nr = r + dx[m]  # m=0: dy[m] = -1 위로 한칸.
        nc = c + dy[m]    # m =1: 오른쪽으로 한칸.

        if (0 <= nr < rr) and (0 <= nc < cc):
            # 1. 방문한 적이 없고,
            # 2. 현재 v 노드에서 i노드로 간선이 연결되어있다면
            if visit[nr][nc] == 0:

                if alpha[nr][nc] not in visited:
                    dfs(nr, nc)
                    count = max(count, len(visited))
                    visited.pop()
    visit[r][c] = 0


dfs(0, 0)
print(count)

해설

진짜 추가 조건이란 조건은 다 붙혀봤는데 자꾸 시간초과,... 아무튼 예제는 다 맞으니 아무튼 난 맞춘거임.

시간 초과의 주원인은 in 함수라고 본다. 시간 복잡도가 O(N)이기에...

 

정답 풀이

import sys

input = sys.stdin.readline
r, c = map(int, input().split())
arr = [list(map(lambda x: ord(x) - 65, input().rstrip())) for _ in range(r)]
#input으로 받은 알파벳들을 아스키코드 화  ex) A = 65 
#그후 - 65를 해 alpha의 각 인덱스가 A,B,C... 에 대응하게 변환 A = 0, B = 1...
alpha = [0] * 26

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


def dfs(x, y, count):
    global ans
    ans = max(ans, count)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < r and 0 <= ny < c and alpha[arr[nx][ny]] == 0:
#특정 인덱스의 값이 0인지 아닌지만 확인하면 되기에 시작복잡도 낮음!

            alpha[arr[nx][ny]] = 1
            dfs(nx, ny, count + 1)
            alpha[arr[nx][ny]] = 0

            #백트래킹 방식으로, 방문 후 돌아나올때 초기화.


ans = 1
alpha[arr[0][0]] = 1
#시작점의 알파벳은 미리 방문 처리
dfs(0, 0, 1)
print(ans)

출처:https://kyun2da.github.io/2020/09/23/alphabet/

 

해석

놀랍게도 정답 방식으로 구현해도 dfs 특징인지 pypy3로 해야만 통과가 된다. (x) 통과가 안된다. dfs에 파이썬으로는 안될지도...

 

in을 해결했음에도 시간 복잡도가 높다는 점은 주목할만 하다. dfs 특성상 모든 가능한 경우의 수를 전부 탐색하기 때문인것 같다.

 

 

 풀이

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


def bfs():
    result = 1
    queue = set([(0, 0, board[0][0])])

    while queue:
        x, y, visited = queue.pop()
        # visited엔 여태껏 방문한 알파벳이 순서대로 저장 ex) HFA

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue

            # 지금의 경로에서 방문 한 적 없는 알파벳일 경우
            elif board[nx][ny] not in visited:

                # visited에 다음 방문할 알파벳을 붙혀준다 ex) HFA + B
                next_visited = visited+board[nx][ny]
                # 중복관리를 위한 set이기에 append가 아닌 add 해준다.
                queue.add((nx, ny, next_visited))
                # 최대 길이를 탐색해야하기 위함
                result = max(result, len(next_visited))

    return result


r, c = map(int, input().split())
board = []

for i in range(r):
    board.append(list(input()))

print(bfs())

출처:https://velog.io/@bye9/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-1987-%EC%95%8C%ED%8C%8C%EB%B2%B3

 

해석

bfs알고리즘을 적용할경우 dfs와 다르게 경로가 보장되지 않는다. 너비 우선 탐색이기 때문. 이를 위해 visited에 지나온 알파벳들을 저장해 경로를 따로 저장해가며 알파벳이 지나온 경로에 포함된지를 체크한다.