Hyuns Kim

Hyuns Kim

Learn, Run 👨‍💻🏃‍♂️

[백준] 알파벳

[백준] 알파벳

풀이

이 문제는 문자열 그래프가 주어질 때 방문한 문자열에 없는 문자만을 골라서
길을 따라갔을 때, 최대 길이를 구하는 문제이다.

전형적인 bfs, dfs 문제라고 생각해서 dfs를 이용해서 풀었다.
visit를 갖고 가면서 방문했을 때 넣어주고 조건문을 이용해 그 방문한 문자열들 안에 있다면 dfs에 넣지 않고 최대 값을 계속 생성해준다.

첫번째는 방문한 알파벳을 visit에 추가시켜주고 백트래킹을 하는 방법이고,
두번째는 방문한 알파벳을 visit에 메모이제이션을 시켜서 백트래킹을 하는 방법이다.
세번째는 방문한 알파벳을 문자열로 취급해서 max answer를 찾는다.(좌우상하)

백트래킹의 설명은 링크를 참고 하자.
알고리즘 정의에 대한 설명은 나중에 제대로 공부하고 포스팅 해보자.


# dfs - 시간초과 에러
import sys
R, C = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
answer = 1
visit = [graph[0][0]]
def dfs(x, y, graph, ans):
    global answer, dx, dy, visit
    answer = max(answer, ans)
    for i in range(4):
        mx, my = x + dx[i], y + dy[i]
        if 0 <= mx < len(graph) and 0 <= my < len(graph[0]) and graph[mx][my] not in visit:
            visit.append(graph[mx][my])
            dfs(mx, my, graph, ans+1)
            visit.remove(graph[mx][my])

def solution(R, C, graph):
    global answer
    dfs(0, 0, graph, 1)
    return answer

print(solution(R, C, graph))

# dfs - 시간초과 에러 수정 메모이제이션 이용

import sys
R, C = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def dfs(x, y, ans):
    global answer
    answer = max(answer, ans)
    for i in range(4):
        mx, my = x + dx[i], y + dy[i]
        if 0 <= mx < len(graph) and 0 <= my < len(graph[0]) and visit[ord(graph[mx][my])-65] == 0:
            visit[ord(graph[mx][my])-65] = 1
            dfs(mx, my, ans+1)
            visit[ord(graph[mx][my])-65] = 0

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

# bfs
import sys

R, C = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def bfs(x, y, visit):
    q = [[x, y, visit]]
    global answer
    while q:
        x, y, visit_n = q.pop()
        for i in range(4):
            mx, my = x + dx[i], y + dy[i]
            if 0 <= mx < len(graph) and 0 <= my < len(graph[0]) and graph[mx][my] not in visit_n:
                q.append([mx, my, visit_n + graph[mx][my]])
        answer = max(len(visit_n), answer)

answer = 1
bfs(0, 0, graph[0][0])
print(answer)

실수 및 배운 점

  • 그냥 dfs만을 이용해서 풀면 시간초과가 계속 나게 되었다.
    if문을 통해 visit에 있는 알파벳을 ‘탐색’하는 과정에서 시간이 조건에 따라 소요가 많이 되었기 때문인 것 같다.

  • dfs에서 visit에 한번 접근할 때, if ~ in visit 을 이용하면 list안에서 한번 더 ‘찾는’ 과정이기 때문에
    비효율적인 탐색 과정이 있을 수 있어 시간초과가 뜨는 것 같다.
    그래서 dp에서 이용했던 ‘메모이제이션’을 이용해서 백트래킹을 이용했다.

  • bfs에서는 deque를 이용했는데 자꾸 메모리 초과가 떴다. 그래서 list, set을 이용해서 했더니 성공했다.
    음.. 왜 그런건지 이유를 정말 못 찾긴 했다.
    책을 찾아서.. 정확히 알아야할 것 같다.

참고