[코테] 알파벳

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

1987번: 알파벳

문제요약:

같은 알파벳을 두번  지날 수 없을 때, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오

 

난이도:

골드4

 

소요시간 , 제출횟수:

@

 

1차 코딩:

r,c = map(int,input().split())

arr = [list(input().strip()) for _ in range(r)]

dy = [-1,0,1,0]
dx = [0,1,0,-1]
m =1

def dfs(y,x,cost,visited):
    global m
    
    for i in range(4):
        ny = y+dy[i]
        nx = x+dx[i]
        if 0<=ny<r and 0<=nx<c and arr[ny][nx] not in visited:
            dfs(ny,nx,cost+1,visited|set([arr[ny][nx]]))
            m =max(m,cost+1)

dfs(0,0,1,set([arr[0][0]]))
#y,x,cost,visited

print(m)

 

2차 코딩:

r,c = map(int,input().split())

arr = [list(input().strip()) for _ in range(r)]

dy = [-1,0,1,0]
dx = [0,1,0,-1]
m =1
visited = set([arr[0][0]])

def dfs(y,x,cost):
    global m
    
    for i in range(4):
        ny = y+dy[i]
        nx = x+dx[i]
        if 0<=ny<r and 0<=nx<c and arr[ny][nx] not in visited:
            visited.add(arr[ny][nx])
            dfs(ny,nx,cost+1)
            m =max(m,cost+1)
            visited.remove(arr[ny][nx])

dfs(0,0,1)
#y,x,cost,visited

print(m)

사실 코딩 자체는 금방했고, 계속 안돼서 이래 저래 시도해보다가 결국 답지를 본 문제입니다. 사실 계속 내가 거쳐왔던 곳들을 저장하고 비교해가면 전진한다는 컨셉은 똑같지만 이를 변수로 계속 가져가면 메모리가 그만큼 계속 할당 되기 때문에, 그리고 dfs로 한 번 실행되면 remove로 지우기 전에 계속 vistied가 유지 되기 때문에 다음과 같이 작성해야 메모리 초과를 피할 수 있습니다. 예전에 2차원 배열에서 세개의 벽을 설치하는 예제에서도 비슷하게 푼 적이 있는데 dfs일때는 이를 저장하지말고  그때 그때 처리하는 것이 더 효율적인것을 기억해야 할 것 같습니다.