[백준] 1987 : 알파벳 (파이썬)

 

그리디, 백트래킹 문제

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

---

접근 방식 

백트래킹

---

💡 풀이코드 (Pypy3 성공 - DFS)

import sys 
r, c = map(int, sys.stdin.readline().split())
graph = []
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
visited= [[False] * c for _ in range(r)]
ans = 0
alpha = set()

# print(visited)

for _ in range(r):
    l = list(map(str, sys.stdin.readline().strip())) # 문자열 하나하나씩 저장
    alpha.update(l) # ['H', 'M', 'C', 'H', 'H']를 한번에 각각의 요소별로 set에 추가
    graph.append(l)

# used = [graph[0][0]] # (0,0)은 시작좌표이므로 무조건 지남
used = set()
used.add(graph[0][0])

def dfs(level, x, y):
    global used, ans
    
    ans = max(ans, level)

    if level == len(alpha):
        return
    
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0 <= ny < r and 0 <= nx < c:
            if visited[ny][nx] == False:
                # if graph[ny][nx] not in used:
                #     visited[ny][nx] = True
                #     used.append(graph[ny][nx])
                #     dfs(level + 1, nx, ny)
                #     used.pop()
                #     visited[ny][nx] = False
                if graph[ny][nx] not in used:
                    visited[ny][nx] = True
                    used.add(graph[ny][nx])
                    dfs(level + 1, nx, ny)
                    used.remove(graph[ny][nx])
                    visited[ny][nx] = False

dfs(1, 0, 0)
print(ans)

 

위의 코드에서 주석을 풀고, 주석 아래 코드를 주석하면 시간초과가 발생한다.

즉, 알파벳을 썼는지를 기록하는 used를 set이 아닌 list 자료구조를 쓰면 시간초과가 발생한다.

 

그러므로, dfs나 알고리즘 문제를 풀 때 해당 원소를 썼는지/안썼는지를 확인하기 위한 자료구조로는 왠만하면 set을 사용하자.

---

참고문헌

https://codinghejow.tistory.com/215

[Python] 백준 1987번 : 알파벳