[백준] 1987번 알파벳 ( 파이썬)

 

문제

 

1987번: 알파벳

 

 

 

풀이 (Python)

 

import sys
input=sys.stdin.readline

# A~Z 는 아스키코드로 65부터 26개이다.

y_max,x_max=map(int,input().split())                
arr=[]
for _ in range(y_max):arr.append(list(map(ord,list(input()))))  # ord를 통해 아스키코드로 변환
visited=[False]*26      # 방문 여부 확인

result=0
# d[0]:우 d[1]:좌 d[2]:상 d[3]:하
dx=[1,-1,0,0]   
dy=[0,0,1,-1]

def dfs(level,y,x):                 # level = 깊이
    global result
    if level>result:result=level    # 최댓값 비교 
    for i in range(4):              # 상하좌우방향 모두 비교
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<x_max and 0<=ny<y_max:     # nx, ny 범위 비교
            tmp=arr[ny][nx]-65
            if not visited[tmp]:    
                visited[tmp]=True      # 방문 처리
                dfs(level+1,ny,nx)
                visited[tmp]=False  # 이미 탐색하고 다시 돌아온 경우 이기에 False처리를 반드시 해야한다.
visited[arr[0][0]-65]=True      # 초기값 방문 처리
dfs(1,0,0)
print(result)

 

 

설명  (Python)

 

필자는 이거 풀다가 울뻔했다.

저 스크린샷이 다가 아니라 다음페이지까지 있다.

질문게시판에서도 별 소득이 없는 문제이다.

알파벳 문제는 제한시간이 굉장히 타이트하게 설정되어 있기에, 시간초과 때문에 꽤 애를 먹었다. dfs풀이 방법 중에서는 거의 더 줄일 곳이 없었기에 pypy로 채점을 진행했는데,

pypy로 채점을 진행하는 경우 메모리초과가 발생한다.

위의 해결책들을 아래에서 다시 언급하겠다.

 

 

 

 

 

Point 1)  dx와 dy를 활용하여 상하좌우 탐색

 

    dx=[1,-1,0,0]               # 방향 선택
    dy=[0,0,1,-1]

 

위의 dx, dy와 현재 x, y값이 있다면 for문을 통해 간단하게 상하좌우를 검사 할 수 있다.

이와 같은 로직을 모르는 경우 if ~~~~ x4 if문을 4번을 사용하여 검사하기 때문에 가독성이 떨어지고, 코드가 길어진다.

하지만 위의 dx, dy를 활용하는 경우 아래와 같이 간결하게 표현이 가능하다.

 

for i in range(4):
    nx,ny=x+dx[i],y+dy[i]   # i값 변화에 대해 x, y값 상하좌우 변동

 

Point 2)  DFS함수

 

def dfs(level,y,x):                 # level = 깊이
    global result
    if level>result:result=level    # 최댓값 비교 
    for i in range(4):              # 상하좌우방향 모두 비교
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<x_max and 0<=ny<y_max:     # nx, ny 범위 비교
            tmp=arr[ny][nx]-65
            if not visited[tmp]:    
                visited[tmp]=True      # 방문 처리
                dfs(level+1,ny,nx)
                visited[tmp]=False  # 이미 탐색하고 다시 돌아온 경우 이기에 False처리를 반드시 해야한다.

 

0,0 좌표에서 출발하여 이미 방문한 알파벳은 방문하지 않고, 최대한 많이 움직인 횟수를 찾으면 되는 문제로

DFS(깊이 우선 탐색)의 깊이(level)의 최댓값을 찾으면 되는 문제이다.

알파벳은 A( 아스키코드 65 )부터 총 26개로 알파벳 기준으로 visited함수를 구현하였다.

 

 

global result
if level>result:result=level

매 dfs함수 호출 떄 마다 깊이의 최댓값을 갱신하기 위해 위와 같이 작성하였다.

 

 

문자열을 아스키코드로 변환하는 함수인 ord함수를 활용하여 아래와 같이 리스트를 입력받았다.

for _ in range(y_max):arr.append(list(map(ord,list(input()))))

이후 visited[tmp]의 tmp를 arr [ny][nx]-65로 구성하였다.

 

Point1을 활용하여 상하좌우 탐색시에 

if not visited[tmp]:    
    visited[tmp]=True      # 방문 처리
    dfs(level+1,ny,nx)
    visited[tmp]=False

방문하지 않았다면 방문처리 후 dfs(level+1,ny,nx)를 호출하였다.

이때 호출한 dfs가 지속적으로 상하좌우 탐색이 불가능해져 종료가 되었을 시

다른 dfs함수가 현 좌표를 거쳐 갈 수 있으므로, 반드시 visited [tmp]=False처리를 해야 한다.

간단한 예제의 경우 False처리를 하지 않아도 오류가 발생하지 않지만 예제 3과 같이 5*5 size의 list만 되어도 오류가 발생한다.

 

Point 3) 시간초과와 메모리초과 해결

백준 채점 언어로

python3의 경우 메모리가 넉넉하고 작동시간이 느린 편이고, pypy3의 경우 메모리가 부족하고 작동시간에 유리하다.

알파벳 문제의 경우 n의 범위가 20이므로 최대 20*20의 리스트를 받아들인다.

입력시간을 줄이기 위해 

import sys
input=sys.stdin.readline

sys라이브러리를 활용하여 readline을 통해 시간을 단축하였다.

 

 

또한 필자의 경우 재귀문제가 있는 경우 런타임에러를 방지하기 위해 

import sys
sys.setrecursionlimit(10 ** 6)          # 메모리 초과 방지

sys라이브러리를 활용하는데,

pypy3에서는 메모리 공간이 부족하기에 위처럼 재귀깊이를 강제로 늘린다면, 메모리초과가 발생한다.

 

 

∴python3에서 돌리기에는 시간초과 문제를 겪기에 pypy3로 채점을 하되, 재귀깊이를 변경하지는 않아야 한다.

 

 

 

 

이 문제에서 사소한 코드의 시간복잡도를 찾아보며 코드를 지속적으로 수정하여 제출하였는데, 별로 얻어가는 것은 없었던 거 같다.

답이 오답처리가 되지 않는 이상 많은 시간을 투자하지 않고 다른 DFS/BFS문제를 푸는 것이 현명하다고 생각한다.