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

2025. 4. 3. 14:28·coding test - python/백준
728x90
반응형

 

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

문제 제목: 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로 설정

 

728x90
반응형

'coding test - python > 백준' 카테고리의 다른 글

백준 / 10819번 차이를 최대로 - 순열 / Python 파이썬  (0) 2025.04.04
백준 / 15649번 N 과 M / Python 파이썬  (0) 2025.04.04
백준 / 1357번 뒤집힌 덧셈 / Python 파이썬  (0) 2025.04.03
백준 / 1296번 팀 이름 정하기 / Python 파이썬  (0) 2025.04.03
백준 / 1292번 쉽게 푸는 문제 / Python 파이썬  (0) 2025.04.02
'coding test - python/백준' 카테고리의 다른 글
  • 백준 / 10819번 차이를 최대로 - 순열 / Python 파이썬
  • 백준 / 15649번 N 과 M / Python 파이썬
  • 백준 / 1357번 뒤집힌 덧셈 / Python 파이썬
  • 백준 / 1296번 팀 이름 정하기 / Python 파이썬
sillon
sillon
꾸준해지려고 합니다..
    반응형
  • sillon
    sillon coding
    sillon
  • 전체
    오늘
    어제
    • menu (614)
      • notice (2)
      • python (68)
        • 자료구조 & 알고리즘 (23)
        • 라이브러리 (19)
        • 기초 (8)
        • 자동화 (14)
        • 보안 (1)
      • coding test - python (301)
        • Programmers (166)
        • 백준 (76)
        • Code Tree (22)
        • 기본기 문제 (37)
      • coding test - C++ (5)
        • Programmers (4)
        • 백준 (1)
        • 기본기문제 (0)
      • 공부정리 (5)
        • 신호처리 시스템 (0)
        • Deep learnig & Machine lear.. (41)
        • Data Science (18)
        • Computer Vision (17)
        • NLP (40)
        • Dacon (2)
        • 모두를 위한 딥러닝 (강의 정리) (4)
        • 모두의 딥러닝 (교재 정리) (9)
        • 통계 (2)
      • HCI (23)
        • Haptics (7)
        • Graphics (11)
        • Arduino (4)
      • Project (21)
        • Web Project (1)
        • App Project (1)
        • Paper Project (1)
        • 캡스톤디자인2 (17)
        • etc (1)
      • OS (10)
        • Ubuntu (9)
        • Rasberry pi (1)
      • App & Web (9)
        • Android (7)
        • javascript (2)
      • C++ (5)
        • 기초 (5)
      • Cloud & SERVER (8)
        • Git (2)
        • Docker (1)
        • DB (4)
      • Paper (7)
        • NLP Paper review (6)
      • 데이터 분석 (0)
        • GIS (0)
      • daily (2)
        • 대학원 준비 (0)
      • 영어공부 (6)
        • job interview (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    programmers
    소수
    백준
    Python
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
sillon
백준 / 1987번 알파벳 / Python 파이썬
상단으로

티스토리툴바