[백준] 1987.알파벳

문제 바로가기

문제 풀이

bfs로 검색 -> 시간초과 발생
dfs로 풀이 -> 해당 위치에서의 방문 여부를 list로 구현하기보다 True/False로 구현하는 것이 더 편리, 이 때 ord()를 사용해서 그 idx를 파악했다.

• visited=[]로 리스트에 해당 문자가 존재하는지 여부를 파악하는 것을 조건문으로 걸었다. 이 때 반드시 방문이 끝날 때는 마지막 방문에서 더 이상의 움직임이 이뤄지지 않았으므로 방문처리를 취소한다.(pop(), or True->False) 이와 같은 방법은 시간초과가 발생했는데 list에 append하고 search하는 과정의 시간복잡도가 O(n)인 반면에 visited=[False]*26은 idx로 접근할 수 있기 때문에 그 시간복잡도가 O(1)이다.

정답 코드

"""
https://www.acmicpc.net/problem/1987
"""
R,C=map(int,input().split())
board=[list(input().rstrip()) for _ in range(R)]
visited = [False]*26 # 알파벳 수 26
# 상하좌우
dx=[-1,1,0,0]
dy=[0,0,-1,1]

max_distance=0

def dfs(x,y,distance):
    global max_distance
    max_distance=max(max_distance, distance)
    visited[ord(board[x][y])-ord('A')]=True
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        # 이동할 수 있는 경우라면
        if 0<=nx<R and 0<=ny<C and not visited[ord(board[nx][ny])-ord('A')]:
            dfs(nx,ny,distance+1) # 그 위치에서 다시 dfs탐색 시작

    visited[ord(board[x][y]) - ord('A')] = False # 이동할 수 없다면 해당 위치 방문 취소

dfs(0,0,1)
print(max_distance)

추가적인 개념 (optional)

dfs에서의 순환함수

• 가능한 모든 경로 탐색: 이 문제에서는 알파벳을 이동하면서 최대한 많은 알파벳을 방문하는 것이 목표입니다. DFS를 사용하면 모든 가능한 경로를 탐색할 수 있습니다. DFS는 한 경로를 끝까지 탐색하고 나서 다른 경로로 넘어가는 방식으로 동작하므로, 가능한 많은 알파벳을 방문하는 경로를 찾을 수 있습니다.

• 백트래킹: DFS는 백트래킹(Backtracking)을 활용하여 불필요한 경로를 더 이상 탐색하지 않고 중단할 수 있습니다. 만약 한 경로가 더 이상 진행할 수 없는 상황(예: 이미 방문한 알파벳)에 놓이면, 이전 단계로 돌아가서 다른 경로를 탐색합니다.(다음 for문 실행 or 더이상 이동할 수 없으면 정지) 이를 통해 효율적으로 가능한 최대 경로를 찾을 수 있습니다.

• 깊이 우선 탐색: 문제에서는 "깊이 우선 탐색"으로 경로를 찾는 것이 자연스럽습니다. 즉, 한 방향으로 최대한 깊게 파고들어가면서 탐색하는 것이 문제의 특성과 잘 어울립니다. DFS는 이러한 탐색 방법을 구현하기에 적합합니다.
  <-> BFS를 사용하지 않은 이유

다른 사람 코드 (optional)(feat.gpt)

# 입력 받기
R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]

# 방문한 알파벳 체크용 배열
visited = [False] * 26

# 상, 하, 좌, 우 이동 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 최대 이동 거리 초기화
max_distance = 0

# DFS 함수 정의
def dfs(x, y, distance):
    global max_distance
    max_distance = max(max_distance, distance)

    # 현재 알파벳 방문 처리
    visited[ord(board[x][y]) - ord('A')] = True

    # 네 방향으로 이동
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < R and 0 <= ny < C and not visited[ord(board[nx][ny]) - ord('A')]:
            dfs(nx, ny, distance + 1)

    # 현재 알파벳 방문 해제
    visited[ord(board[x][y]) - ord('A')] = False

# 시작 위치는 (0, 0)부터 시작
dfs(0, 0, 1)

print(max_distance)