[백준/python] 1987번_알파벳(DFS)

📌문제 유형

DFS, BFS(골드 4)

 

📌문제

1987번: 알파벳

 

📌나의 문제풀이

- 1%에서 틀려버림,,

r, c = map(int,input().split())

maps = []
for _ in range(r):
    rows = list(map(str, input()))
    maps.append(rows)

def dfs(x,y):
    # print(alpha, visited)
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx >= 0 and nx < r and ny >= 0 and ny < c:
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1

                if maps[nx][ny] in alpha:
                    continue
                else:
                    alpha.append(maps[nx][ny])
                    dfs(nx,ny)
                    # visited[nx][ny] = 0
                    # alpha.pop(len(alpha)-1)

    # dfs(nx+1, ny)
    # dfs(nx, ny+1)
       


visited = [[0 for _ in range(c)] for _ in range(r)]
visited[0][0] = 1
alpha = [maps[0][0]]
dfs(0,0)

print(visited)
print(alpha)
print(len(alpha))

 

📌다른사람의 문제풀이

 - DFS

[Python] 백준 1987번 : 알파벳

[BOJ][Python] 백준 1987번 - 알파벳

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = [list(map(lambda x:ord(x)-65, input())) for _ in range(r)]
alpha = [False] * 26
max_ = 1
d = [(1,0), (-1,0), (0,1), (0,-1)]

def DFS(x, y, cnt):
    global max_
    max_ = max(max_, cnt)
    
    for i in range(4):
        nx, ny = x + d[i][0], y + d[i][1]
        
        if 0 <= nx < r and 0 <= ny < c:
            if not alpha[board[nx][ny]]:
                alpha[board[nx][ny]] = True
                DFS(nx,ny,cnt+1)
                alpha[board[nx][ny]] = False
                    
alpha[board[0][0]] = True
DFS(0,0,max_)
print(max_)

r, c = map(int, input().split())
maps = []
for _ in range(r):
    maps.append(list(input()))
ans = 0
alphas = set()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, count):
    global ans
    ans = max(ans, count)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c and not maps[nx][ny] in alphas:
            alphas.add(maps[nx][ny])
            dfs(nx, ny, count+1)
            alphas.remove(maps[nx][ny])
alphas.add(maps[0][0])
dfs(0, 0, 1)
print(ans)

 

📌리뷰

- DFS,BFS는 종료 조건이 없으면 어쨌든 모든 구간을 다 순회한다 -> 위치visited는 필요 없음 

- if문에서 해당 알파벳이 포함되어 있는지 확인 -> 포함되어 있으면 종료, 아니면 진행