Algorithm/백준
[Python] 1987 알파벳(dfs)
내영잉
2023. 1. 19. 21:00
1. 문제 📚
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
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)