(Python/🥇5)백준알고리즘 1987번: 알파벳

백준 알고리즘 알파벳

 

문제:

 

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력:

 

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력:

 

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

풀이:

 

처음 내가 생각한 방법은 bfs와 set을 이용하는 것이였다. 

 

import sys
from collections import deque

R, C = map(int, input().split())
maps = [list(sys.stdin.readline().rstrip()) for _ in range(R)]

q = deque()
q.append((0, 0))
sets = set()
sets.add(maps[0][0])  # 시작 위치 알파벳 추가

while q:
    x, y = q.popleft()
    move = [(1, 0), (-1, 0), (0, -1), (0, 1)]
    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < R and 0 <= ny < C and maps[nx][ny] not in sets:
            sets.add(maps[nx][ny])
            q.append((nx, ny))

print(len(sets))

하지만 테스트케이스중에 마지막꺼가 틀리면서 되지않는다.

 

최단 거리를 찾는것이 아닌 가장 멀리가는 것을 찾는것이기 때문에 큐를 사용하지 않아도 되고, bfs진행할때마다 지나온 문자열들을 따로 넣어주면서 최댓값을 최신화 시켜주기로 했다.

 

R,C = map(int,input().split(" "))
maps =[[i for i in sys.stdin.readline().rstrip()] for i in range(R)]

def bfs():
    move = [(1,0),( -1,0),(0,-1),(0,1)]
    result = 0
    q = set([(0, 0, maps[0][0])])
    while q:
        x, y, ck = q.pop()
        result = max(result, len(ck))
        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if R > nx >= 0 and C > ny >= 0 and maps[nx][ny] not in ck:
                q.add((nx, ny, maps[nx][ny] + ck))
    return result
print(bfs())

 

dfs는 이렇게 한다고 한다.

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


def dfs(x, y, cnt):
    global ans

    ans = max(ans, cnt)
    visited.add(graph[x][y])

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

        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] not in visited:
                dfs(nx, ny, cnt + 1)
    visited.remove(graph[x][y])


dfs(0, 0, 1)

print(ans)

visited.remove로 지나온 것을 다시 삭제해주는것 같다. 백트래킹을 사용하는것 같다.