백준 / 1987번 알파벳 / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 1987번 알파벳

문제 사이트: https://www.acmicpc.net/problem/1987

 

---

나의 풀이 (시간초과)

 

흠.. 최대한 최적화 했다고 생각했는데 아니였나보다

 

한번 더 풀어볼 것

import sys
from collections import deque
input = sys.stdin.readline
r,c = map(int,input().split())

maps = []
set_maps = set()
directions = ((1, 0), (0, 1),(0, -1),(-1, 0))
max_len = 1
for i in range(r):
    tmp = list(input().rstrip())
    maps.append(tmp)
    for j in tmp:
        set_maps.add(j)

visited = [[False] * c for i in range(r)]
visited[0][0] = True
lst = deque([maps[0][0]])
def dfs(y,x,n):
    global max_len, lst
    if max_len < n:
        max_len = n
    if n == len(set_maps):
        max_len = len(set_maps)
        return
    if len(set_maps) == 26 and (r*1)*(c+1) == 26:
        max_len = len(set_maps)
        return
    for i in range(4):
        ny = y + directions[i][0]
        nx = x + directions[i][1]
        if 0 <= ny < r and 0 <= nx < c and visited[ny][nx] == False:
            if maps[ny][nx] not in lst:
                visited[ny][nx] = True
                lst.append(maps[ny][nx])
                dfs(ny,nx,n+1)
                visited[ny][nx] = False
                lst.pop()


dfs(0,0,1)
print(max_len)

 

모범답안 - visited -> set으로 관리

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
maps = [list(input().strip()) for _ in range(r)]

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
max_len = 0

def dfs(y, x, visited_set):
    global max_len
    max_len = max(max_len, len(visited_set))

    for dy, dx in directions:
        ny, nx = y + dy, x + dx
        if 0 <= ny < r and 0 <= nx < c:
            ch = maps[ny][nx]
            if ch not in visited_set:
                visited_set.add(ch)
                dfs(ny, nx, visited_set)
                visited_set.remove(ch)  # 백트래킹

dfs(0, 0, set(maps[0][0]))
print(max_len)

 

 

 

시간 에바다..

 

 

다른 풀이 ord 사용

def dfs(y, x, visited_mask, count):
    global max_len
    max_len = max(max_len, count)

    for dy, dx in directions:
        ny, nx = y + dy, x + dx
        if 0 <= ny < r and 0 <= nx < c:
            char_bit = 1 << (ord(maps[ny][nx]) - ord('A'))
            if not visited_mask & char_bit:
                dfs(ny, nx, visited_mask | char_bit, count + 1)

start_bit = 1 << (ord(maps[0][0]) - ord('A'))
dfs(0, 0, start_bit, 1)
print(max_len)

 

ord는 비트마스크를 사용한 것으로, 문자열을 아스키코드 인덱스로 바꿔줌

예시

ord('A')   # 65
ord('B')   # 66
ord('Z')   # 90

ord('a')   # 97
ord('z')   # 122

 

---

※ 알아야 할 것

-  alpha = ord(maps[ny][nx]) - ord('A')  # A~Z → 0~25

- visited_mask = 0
visited_mask |= (1 << alpha)   # alpha번째 비트를 1로 설정