[모각코] 210811 Today I Learned

https://amor-fati.tistory.com/41

[모각코] 210804 Today I Learned

지난 주에 visited 리스트가 재귀함수를 빠져나와도 변경된 값이 계속 유지되어서 문제가 된다고 했었는데, 그냥 copy가 아닌 copy.deepcopy() 함수만 쓰면 됐다. 예전에 쓴 적 있는데 까먹고 있었다. 바보 ㅎㅋ

그런데 코드를 고치고 생각해보니 visited 리스트 자체가 필요 없었다. 이번 문제는 이전에 지나간 곳도 아니고, 지나온 알파벳도 아니어야 하기 때문에 지나온 알파벳들을 저장하는 before 리스트에서 다음 지나가려는 알파벳이 있는지만 확인하면 됐다. visited로 굳이 비교하지 않아도 된다. 다음 방문하려는 알파벳이 before 안에 있다는 건 이미 방문을 했다는 걸 의미하니까! (혹은 동일 알파벳을 지나온 것. 어쨌든 그 곳으로 이동하지 못 함)

 

그렇게 visited 리스트도 빼고 코드도 다시 고쳤는데 시간초과 실화니 ,,

dfs 자체를 뜯어 고쳐야 되는 것 같다 ,, 문제 검색해보니까 다들 나랑 완전 다른 방법으로 했다. 처음 보는 거임 환장

dfs 구현하는 다른 코드 공부한 다음에 풀어야 할 것 같다 .. ^^

 

 

** 타임아웃 코드

import sys
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, p, R, C, before):
    before.append(p.value)
    next = Node(bord)

    if p.col < C-1:   # 오른쪽 이동
        if 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_before = copy.deepcopy(before)
            Move(bord, next, R, C, n_before)
    if p.col > 0:   # 왼쪽 이동
        if 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_before = copy.deepcopy(before)
            Move(bord, next, R, C, n_before)
    if p.row > 0: # 위쪽 이동
        if 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_before = copy.deepcopy(before)
            Move(bord, next, R, C, n_before)
    if p.row < R-1: # 아래쪽 이동
        if 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_before = copy.deepcopy(before)
            Move(bord, next, R, C, n_before)
    else:
        global max_count
        if max_count < len(before):
            max_count = len(before)

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

before = [] # 지나온 알파벳 저장

# 출력
p = Node(bord)
Move(bord, p, R, C, before)
print(max_count)