[백준 1987번] 알파벳 문제 풀이 (with Python)

 

< 문제 >

 

 

< 입출력 >

 

 

< TRY1 > - 틀렸습니다.

from collections import deque

R, C = map(int,input().split())
arr =[]
for i in range(R):
    arr.append(list(input()))

passed = [] # 지나간 알파벳 목록 저장
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
q = deque()


def dfs(x,y, cnt):
    global result
    result = max(result, cnt)
    print(passed)
    q.append((x, y))
    while(q):
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C and arr[nx][ny] not in passed:
                passed.append(arr[nx][ny])
                q.append((nx, ny))
                dfs(nx, ny, cnt + 1)



result = 0
passed.append(arr[0][0])
dfs(0,0,1)
print(result)

해당 코드의 경우,

< 예시 >

2 3
ABN
BCA

 

< 출력 >

['A']
['A', 'B']
['A', 'B', 'N']
['A', 'B', 'N', 'C']
4

라는 결과가 나온다. ABN 다음에 바로 C로 이동할 수 없으므로, while문을 제거하고, 이동할 수 있는 경우 dfs를 호출하는 방식으로 바꾸어야 한다.

 

 

< TRY 2 > - 시간 초과

from collections import deque

R, C = map(int,input().split())
arr =[]
for i in range(R):
    arr.append(list(input()))

passed = [] # 지나간 알파벳 목록 저장
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
q = deque()


def dfs(x,y, cnt):
    global result
    result = max(result, cnt)
    print(passed)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C and arr[nx][ny] not in passed:
            passed.append(arr[nx][ny])
            dfs(nx, ny, cnt + 1)
            passed.remove(arr[nx][ny])


result = 0
passed.append(arr[0][0])
dfs(0,0,1)
print(result)

 

위의 반례는 해결되었지만, 시간 초과가 난다....😂 

checked를 이용해서, 해당 길을 시도해봤으면 다시 시도하지 못하도록 해야겠다.