[Python] 백준 1987번 : 알파벳

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

1987번: 알파벳

---

 문제 풀이

DFS 문제이다.

 

재귀적으로 DFS를 구현하는데 재귀를 끝내고 나오면 이전에 포함시킨 알파벳을 지움으로

약간 백트래킹과 같은 모습을 가지게 된다.

2차원 배열로 여러 가지 경우가 생길 수 있으므로 최댓값 global 변수로 지정해 계속 최신화해준다.

 느낀 점

시간 초과로 한번 수정, 또 수정 계속 수정하다가 어이가 없어서 다른 분의 코드를 보고 아스키코드로 접근해서 풀어보려고 했다. 근데 또 시간 초과가 발생하길래 pypy3로 제출했더니 정답.. 진짜 화가 난다.

그렇게 시간을 따지는 게 의미 있는 게 아닌 것 같다. DFS 구현을 어떻게 할지만 연습했다고 생각해야겠다.

 코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = [list(map(lambda x:ord(x)-65, input())) for _ in range(r)]
alpha = [False] * 26
max_ = 1
d = [(1,0), (-1,0), (0,1), (0,-1)]

def DFS(x, y, cnt):
    global max_
    max_ = max(max_, cnt)
    
    for i in range(4):
        nx, ny = x + d[i][0], y + d[i][1]
        
        if 0 <= nx < r and 0 <= ny < c:
            if not alpha[board[nx][ny]]:
                alpha[board[nx][ny]] = True
                DFS(nx,ny,cnt+1)
                alpha[board[nx][ny]] = False
                    
alpha[board[0][0]] = True
DFS(0,0,max_)
print(max_)

### Set() 풀이
import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = [list(input().strip()) for _ in range(r)]
alpha = set(board[0][0])
max_ = 0
d = [(1,0), (-1,0), (0,1), (0,-1)]

def DFS(x, y, cnt):
    global max_
    max_ = max(max_, cnt)
    
    for i in range(4):
        nx, ny = x + d[i][0], y + d[i][1]
        
        if 0 <= nx < r and 0 <= ny < c:
            if board[nx][ny] not in alpha:
                alpha.add(board[nx][ny])
                DFS(nx, ny, cnt+1)
                alpha.remove(board[nx][ny])
                
DFS(0,0,max_)
print(max_)