[BOJ] 1987. 알파벳

1일 1PS 4일차!

문제

---

골드 4

• DFS 를 활용하면 되고 이때 Path 를 함께 저장하면 된다.
• 편하게 Stack 을 두 개 활용해서 (x, y, cnt) 와 path 를 각각 저장하면서 DFS 했지만 시간 초과로 합쳐주니 바로 통과했다.
• set() 에서 집합에 특정 Element 가 있는 지 확인할 때 O(1)

포인트

---

1. DFS
2. DFS 와 함께 지나온 Path 를 함께 추가

코드

---

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

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

matrix = []
for _ in range(r):
    matrix.append(input())

stack = set()
max_cnt = 0

stack.add((0, 0, 1, matrix[0][0]))

while stack:
    x, y, cnt, path = stack.pop()
    max_cnt = max(max_cnt, cnt)

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

        if temp_x < 0 or temp_x >= r: continue
        if temp_y < 0 or temp_y >= c: continue

        if matrix[temp_x][temp_y] not in path:
            stack.add((temp_x, temp_y, cnt + 1, path + matrix[temp_x][temp_y]))

print(max_cnt)