[Python] 1987 알파벳(dfs)

1. 문제 📚

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

1987번: 알파벳

2. 입출력 예 📋

3. 알고리즘 ✅

그래프 문제 + 백트래킹 문제이다 

조건이 이미 한번 지나온 알파벳은 방문할 수 없음이므로 앞으로 나아갈 곳이 이미 지나온 알파벳이라면 뒤로 가서 다시 탐색을 해주어여한다 

bfs로 count를 세어준다음, 가장 최대값을 리턴해주었다!

여기서 포인트는 재귀호출이 끝나면 다시 False로 바꿔주어 탐색을 해주어야한다

4. 소스코드 💻

import sys

input = sys.stdin.readline

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

visited = { 'A': False, 'B': False, 'C': False, 'D': False, 'E': False, 'F': False,
'G': False, 'H': False, 'I': False, 'J': False, 'K': False, 'L': False,
'M': False, 'N': False, 'O': False, 'P': False, 'Q': False, 'R': False,
'S': False, 'T': False, 'U': False, 'V': False, 'W': False, 'X': False,
'Y': False, 'Z': False }

answer = 0
def dfs(x, y, cnt):
    global answer
    answer = max(cnt, answer)
    dx, dy = [0, 0, -1, 1], [1, -1, 0, 0]
    visited[graph[x][y]] = True
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < R and 0 <= ny < C:
            if not visited[graph[nx][ny]]:
                visited[graph[nx][ny]] = True # 조건
                dfs(nx, ny, cnt + 1)
                visited[graph[nx][ny]] = False # 재귀 호출이 끝나면 False로 바꿔줌

dfs(0, 0, 1)

print(answer)

 

 

위에 코드로 진행하니 33 퍼정도에서 시간초과가 떴다 ㅜㅜ 다른사람들 코드를 참고해보니

아래 방식과 같이 ord를 이용해서 알파벳 방문여부를 진행하는 것을 보고 수정해서 제출했돠

 

import sys

input = sys.stdin.readline

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

visited = [False for _ in range(26)]

answer = 0
def dfs(x, y, cnt):
    global answer
    answer = max(cnt, answer)
    dx, dy = [0, 0, -1, 1], [1, -1, 0, 0]
    visited[ord(graph[x][y]) - 65] = True
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < R and 0 <= ny < C:
            if not visited[ord(graph[nx][ny]) - 65]:
                visited[ord(graph[nx][ny]) - 65] = True
                dfs(nx, ny, cnt + 1)
                visited[ord(graph[nx][ny]) - 65] = False

dfs(0, 0, 1)

print(answer)