[모각코] 210804 Today I Learned

1987번: 알파벳 (acmicpc.net)

1987번: 알파벳

 

 

또 너무 늦어질 것 같아서 먼저 올리는 완성 안 된 코드 ㅜ

 

import copy

global max_count
max_count = 0

# DFS
class Node:
    def __init__(self, bord):
        self.value = bord[0][0]
        self.row = 0
        self.col = 0

def Move(bord, visited, p, R, C, count, before):
    before.append(p.value)
    next = Node(bord)
    count += 1
    visited[p.row][p.col] = False
    if p.col < C-1:   # 오른쪽 이동
        if visited[p.row][p.col+1] == True and bord[p.row][p.col+1] not in before:
            next.value = bord[p.row][p.col+1]
            next.row = p.row
            next.col = p.col + 1
            n_visited = list(visited)
            n_before = before.copy()
            Move(bord, visited, next, R, C, count, n_before)
    if p.col > 0:   # 왼쪽 이동
        if visited[p.row][p.col-1] == True and bord[p.row][p.col-1] not in before:
            next.value = bord[p.row][p.col-1]
            next.row = p.row
            next.col = p.col - 1
            n_visited = list(visited)
            n_before = before.copy()
            Move(bord, visited, next, R, C, count, n_before)
    if p.row > 0: # 위쪽 이동
        if visited[p.row-1][p.col] == True and bord[p.row-1][p.col] not in before:
            next.value = bord[p.row-1][p.col]
            next.row = p.row - 1
            next.col = p.col
            n_visited = list(visited)
            n_before = before.copy()
            Move(bord, visited, next, R, C, count, n_before)
    if p.row < R-1: # 아래쪽 이동
        if visited[p.row+1][p.col] == True and bord[p.row+1][p.col] not in before:
            next.value = bord[p.row+1][p.col]
            next.row = p.row + 1
            next.col = p.col
            n_visited = list(visited)
            n_before = before.copy()
            Move(bord, visited, next, R, C, count, n_before)
    else:
        global max_count
        if max_count < count:
            max_count = count


# 입력
R, C = map(int, input().split())
bord = []
for i in range(R):
    bord.append(input())
bord.reverse

visited = [[True for _ in range(C)] for _ in range(R)]  # 
before = [] # 지나온 알파벳 저장
# 출력
p = Node(bord)
count = 0
Move(bord, visited, p, R, C, count, before)
print(max_count)

# 새로운 경로로 갈 때 이전 경로에서 지나갔던 곳도 지나갈 수 있음

 

 

미로에서 깊이우선탐색을 통해 경로를 찾는 문제와 비슷하게 풀면 될 것 같다고 생각했다. 방문하지 않은 인접한 칸을 방문하면서 count만 해주면 되는데, 문제는 한 경로가 끝나고 다른 경로로 가게 될 때 visited 리스트가 이전 경로에서 방문하면서 True로 바뀐 값이 그대로 유지되어서 이전에 지나간 칸을 다시 지나갈 수 없다는 거다.

 

예를 들어 보드가 이렇게 돼 있을 때,

CAAB

ADCB

말은 이렇게 두 가지 경로가 지나갈 수 있다.

CAAB    CAAB

ADCB    ADCB  

 

지금 짠 알고리즘이 D가 첫 번째 경로에서 방문되면 두 번째 경로에서는 방문을 할 수 없어 두 번째 경로 카운트가 2가 나온다. (3이 나와야 됨) 대입연산을 썼을 때 리스트의 주소를 참조하는 성질 때문에 재귀함수를 빠져나와도 변경된 값이 유지되는 건가 싶어 copy 함수도 사용하고, list()도 사용해봤는데 변화가 없다 .. 😔 

 

이전에 미로 문제를 풀었을 때는 한 경로가 안 되면 다시 빠꾸해서 다른 경로로 가는데 이때 이전에 지나갔던 곳도 지나갈 수 있었던 것 같은데 .. 이건 왜 안 되는 지 모르겠다. 좀 생각해보는 걸로.