[백준][Python] 1987번 알파벳 - 코팩

https://www.acmicpc.net/problem/1987

1987번: 알파벳

풀이

BFS 문제 풀이를 위해서 기존에 자료구조를 deque으로 사용하였지만 이번에는 set으로 구현해주었습니다.

더군다나 지나온 경로를 일일이 set이나 list에 저장할 경우 메모리 초과가 발생하기에 문자열로 저장해주었습니다.

다음번에는 경로문제가 생길경우에 DFS를 우선시해서 풀어보겠습니다.

 

코드(BFS)

# 1987번 알파벳
dxys = [[1,0],[-1,0],[0,1],[0,-1]]

def bfs():
    # 중복처리를 위해 set사용과 문자열을 이용하서 거쳐온 알파벳을 저장
    queue = set([(0, 0, grid[0][0])])
    visited = [[0] * m for _ in range(n)]
    # 최장 경로의 길이를 저장해줄 변수
    cnt = 0
    while queue:
        cx, cy, path = queue.pop()
        cnt = max(cnt, len(path))
        for dx, dy in dxys:
            nx = cx + dx
            ny = cy + dy
            if 0 <= nx < m and 0 <= ny < n:
                if grid[ny][nx] not in path:
                    n_path = path + grid[ny][nx] 
                    queue.add((nx, ny, n_path))
    return cnt              

n, m = map(int, input().split())
grid = [list(input()) for _ in range(n)]
print(bfs())

코드(DFS)

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)

출처:https://sorryhyeon.tistory.com/34

 

출력결과(BFS로 제출)