[BOJ, 백준] 1987 알파벳 python

 

 

일본에 다녀오고, 여러가지 생각을 정리하면서 간만에 올리는 포스팅이 되겠습니다.

문제는 다음과 같습니다.

 

 

 

 

즉, 이전에 지나오지 않았던 발판으로 얼만큼 늘어날 수 있는가? 라는 문제가 되겠습니다.

 

백트래킹의 교과서 같은 문제 중 하나인 것 같습니다.

 

시간이 좀 여유로울 것 같아서 여러가지 오답 코드를 작성했습니다만 (이전에 방문했던 포인트들을 리스트로 만들어서 하나하나 체크한다던지)

 

결국 등장한 알파벳을 True로 세팅하고, 아닌 경우에는 False로 체크하는 방식으로 진행하는것이 제일 좋아보였습니다.

코드는 다음과 같이 나오겠습니다.

 

R,C = map(int,input().split())
mapp = []
for _ in range (0,R):
    a = input()
    mapp.append(a)

moving = [(0,1),(-1,0),(1,0),(0,-1)]
ans = 0
visited = [False for _ in range (0,26)]
visited[ord(mapp[0][0]) - 65] = True
cnt = 1
def bfs(n,m):
    global ans
    global visited
    global cnt
    ans = max(ans, cnt)
    for k in range (0,4):
        nn,mm = n + moving[k][0], m + moving[k][1]
        if 0 <= nn < R and 0 <= mm < C and visited[ord(mapp[nn][mm]) - 65] == False:
            visited[ord(mapp[nn][mm])-65] = True
            cnt += 1
            bfs(nn,mm)
            visited[ord(mapp[nn][mm])-65] = False
            cnt -= 1
bfs(0,0)
print(ans)