[백준] 1987 알파벳

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

상하좌우칸을 이동하면서 지나온 정보들을 집합으로 저장하여 기록 및 중복 여부를 확인하였습니다.

시간초과를 고려하여 집합을 이용하여 알파벳을 기록하였으나 시간초과가 발생하였습니다.

이후 리스트에서 좌표들의 정보를 가지고 탐색하던것을 중복을 줄이기 위하여 집합을 이용하였습니다.

2) 알고리즘

• DFS

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

dr = [-1, 0, 1, 0]                                              # 위 오른쪽 아래 왼쪽
dc = [0, 1, 0, -1]

def solution():
    global answer

    s = set([(0, 0, board[0][0])])                              # 좌표, 지나온 좌표들의 알파벳 기록 (시간 단축을 위해 일반 리스트가 아닌 집합으로 관리)

    while s and answer < 26:                                    # 탐색할게 아직 남았거나, 알파벳 26개를 모두 찾은 경우 종료
        y, x, ans = s.pop()                                     # 좌표, 발견한 알파벳 기록

        for k in range(4):
            r = y + dr[k]                                       # 다음 좌표
            c = x + dc[k]       

            if 0 <= r < R and 0 <= c < C:
                if board[r][c] not in ans:                      # 현재 좌표의 알파벳이 이전에 지나오지 않았다면
                    s.add((r, c, ans + board[r][c]))            # 집합에 추가
                    answer = max(answer, len(ans)+1)            # 정답 최댓값 갱신

R, C = map(int, sys.stdin.readline().split())                       # 세로, 가로
board = [list(sys.stdin.readline().rstrip()) for _ in range(R)]     # 배열의 정보
answer = 1                                                          # 정답 (시작이 포함되어야 하므로 최소 1)

solution()                                                      # 탐색

print(answer)                                                       # 출력

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

시간초과를 고려하여 방문한 알파벳 목록을 집합으로 관리를 하였지만, 탐색 과정이 길어지면 시간초과가 발생하였습니다.

탐색 과정을 줄이기 위하여 집합을 이용하였습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

1987번: 알파벳

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다