[백준] 1987번 : 알파벳[Python]

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

1987번: 알파벳

 

 

풀이 :

DFS방법 밖에 떠오르지 않아서 DFS방법으로만 풀이하였음

첫번째 풀이 당시 10번이 넘는 시도동안 시간초과가 났고, 이를 해결하지 못하여 다른 사람의 풀이를 참고하여 수정하였음

 

첫번째 방법(시간초과)

1. max_count(몇 칸을 갔는지 저장하기 위한 2차원 리스트) 생성

2. visited(방문여부를 확인하기 위한 2차원 리스트) 생성

3. chk_Alpha(사용한 알파벳을 저장하기 위한 리스트) 생성

4. 매 상황마다 chk_Alpha와 visited 리스트를 deepcopy(깊은복사)하여 백트래킹을 제어 조건으로 사용

5. 상 하 좌 우로 이동한 좌표에 해당하는 알파벳이 chk_Alpha리스트에 들어있지 않고 현재 진행중인 dfs에서 방문하지 않았다면 max_count[ny][nx] = max_count[y][x] + 1 

6. max_count 리스트의 최대값 출력

 

* Tip - (필자의견)

딱 보았을때 문제 자체는 어렵지 않아서 알고리즘은 금방 생각해 내었으나 시간초과로 인해 10번이 넘는 시도를 하였음

-> 첫 풀이에서 deepcopy를 이용하여 매 상황마다 dfs + 백트래킹을 진행하고자 하였으나 dfs 특성상 재귀로 인한 시간을 줄이기 힘들다고 판단하여 알파벳 개수 크기의 리스트를 생성하여 풀이 진행하였음

 

두번째 방법

1. 알파벳 개수(26개) 크기의 리스트 생성

2. DFS 구현

 

 

코드 : 

첫번째 방법(시간초과)

import copy
R,C = map(int,input().split())

graph = []
max_count = [[1] * C for _ in range(R)]
visited = [[False] * C for _ in range(R)]
for i in range(R):
    graph.append(list(input()))

chk_Alpha = []
            
# 상 하 좌 우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

def dfs(y,x,chk_Alpha,visited):
    chk_Alpha_copy = copy.deepcopy(chk_Alpha)
    chk_Alpha_copy.append(graph[y][x])
    visited_copy = copy.deepcopy(visited)
    visited_copy[y][x] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < C and 0 <= ny < R and not visited_copy[ny][nx] and graph[ny][nx] not in chk_Alpha_copy:
            max_count[ny][nx] = max_count[y][x] + 1
            dfs(ny,nx,chk_Alpha_copy,visited_copy)

dfs(0,0,chk_Alpha,visited)
print(max(map(max,max_count)))

 

두번째 방법

R,C = map(int,input().split())

graph = []
visited = [False] * 26  # 알파벳 개수 크기의 리스트 생성     
for i in range(R):
    graph.append(list(input()))

# 상 하 좌 우
dx = [0,0,-1,1] 
dy = [1,-1,0,0]

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

dfs(0,0,answer)
print(answer)