파이썬 알고리즘 284번 | [백준 1987번] 알파벳 - 그래프 이론 dfs

Yunny.Log ·2023년 1월 1일

Algorithm

목록 보기

289/318

284. 알파벳

1) 어떤 전략(알고리즘)으로 해결?

dfs 로 해결

2) 코딩 설명

주석 설명

<내 풀이>


import sys

R, C = map(int,sys.stdin.readline().split())
board = []
disr = [-1,1,0,0]
disc = [0,0,-1,1]
maxx = 0
alphabet = [0 for _ in range(26)] 
# in으로 탐색하지 않고
# 미리 알파벳 배열을 만들어두어 방문 여부 체크하는 것이 중요 ! 

for i in range(R) :
    board.append(list(sys.stdin.readline()))
visited = [[-1]*C for _ in range(R)]

# 초기화 작업 
visited[0][0] = 1
alphabet[ord(board[0][0])-65] = 1

def dfs(r, c, cnt) :
    global maxx
    if cnt>maxx :
        maxx = cnt
        
    for i in range(4) :
    
        if 0<=r+disr[i]<R and 0<=c+disc[i]<C \
            and visited[r+disr[i]][c+disc[i]]==-1:
            ascii = ord(board[r+disr[i]][c+disc[i]])-65
            if alphabet[ascii]==0 :
                visited[r+disr[i]][c+disc[i]]=1
                alphabet[ascii]=1
                # 가지 치기 
                dfs(r+disr[i], c+disc[i], cnt+1)
                # 가지 친 이후로는 복구 작업 
                visited[r+disr[i]][c+disc[i]]=-1
                alphabet[ascii]=0

dfs(0,0,1)
print(maxx)

< 내 틀렸던 풀이, 문제점 >

bfs 로 접근 , 근데 메모리도 그렇고 visit 처리 제대로 안해주는 등의 문제로 인해 틀렸다.


from collections import deque
import sys

r,c = map(int,sys.stdin.readline().split())
board = []
disr = [-1,1,0,0]
disc = [0,0,-1,1]
history = []
visit = []
answer = 1
q = deque()
for i in range(r) :
    board.append(list(sys.stdin.readline()))
visited = [[-1]*c for _ in range(r)]
visited[0][0] = 1
q.append((0,0,0, [board[0][0]] , visited))

while q :
    nowr, nowc, now_cnt, now_his, now_visited  = q.popleft()
    print(nowr, nowc, now_cnt, now_his, now_visited, " hi \n")
    for i in range(4) :
        if 0<=nowr+disr[i]<r and 0<=nowc+disc[i]<c \
            and now_visited[nowr+disr[i]][nowc+disc[i]]==-1 \
            and board[nowr+disr[i]][nowc+disc[i]] not in now_his:
            
            now_his.append(board[nowr+disr[i]][nowc+disc[i]])
            now_visited[nowr+disr[i]][nowc+disc[i]]=1
            q.append((nowr+disr[i], nowc+disc[i], now_cnt+1, now_his, now_visited))
            if answer < len(now_his) :
                answer = len(now_his)
print(answer)

(2) dfs 로 접근했는데 시간초과

from collections import deque
import sys

R, C = map(int,sys.stdin.readline().split())
board = []
disr = [-1,1,0,0]
disc = [0,0,-1,1]
maxx = 0
for i in range(R) :
    board.append(list(sys.stdin.readline()))
visited = [[-1]*C for _ in range(R)]
visited[0][0] = 1

def dfs(r, c, cnt, history) :
    global maxx
    if cnt>maxx :
        maxx = cnt

    for i in range(4) :
        if 0<=r+disr[i]<R and 0<=c+disc[i]<C and visited[r+disr[i]][c+disc[i]]==-1 and board[r+disr[i]][c+disc[i]] not in history:
            visited[r+disr[i]][c+disc[i]]=1
            history.append(board[r+disr[i]][c+disc[i]])
            dfs(r+disr[i], c+disc[i], cnt+1, history)
            visited[r+disr[i]][c+disc[i]]=-1
            history.pop()

dfs(0,0,1,[board[0][0]])

print(maxx)