💯Problem Solving
[BOJ] 1987 알파벳
date
Jul 7, 2023
slug
boj-1987
author
status
Public
tags
Python
BOJ
summary
백준 1987번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Jul 14, 2023 04:37 PM
문제 링크
문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
문제풀이
DFS를 사용해서 depth중 가장 긴 depth를 구하는 것이다.
조건1. Trace안에는 중복 문자열이 없어야 한다.
처음에는 알파벳 자체를 저장하는 리스트를 통해서
x in list 느낌으로 했는데, 시간초과 in이 O(n)이라 오래걸린다
그래서 알파벳 저장하는 배열을 따로 만들지않고
A-Z까지가 있다 라고 표현한 배열을 만들어
인덱스 0 이 A를 나타내게끔했다.
그래서 A가 주어지면 1이 있으면 조건1에 부합하지 않으므로
지금 trace의 길이 -1을 리턴
A가 주어지는데 0이면 trace에 추가후 그 노드를 기준으로 상하좌우 탐색
파이썬 문제풀이 코드
R,C = tuple(map(int, input().split())) board = [] dx = [1, 0, -1, 0] # 동남서북 dy = [0, 1, 0, -1] visited = [[0] * C for _ in range(R)] alphabet_list = [0] * (ord('a') - ord('A') + 1) # 0번째 인덱스가 A를 나타냄 def dfs(y, x, depth): alphabet = ord(board[y][x]) - ord('A') max_depth = 0 if alphabet_list[alphabet] == 0: alphabet_list[alphabet] = 1 else: return depth-1 for i in range(4): if x+dx[i] >= 0 and x+dx[i] < C and y+dy[i] >= 0 and y+dy[i] < R: cur_depth = dfs(y+dy[i], x+dx[i], depth+1) # print(alphabet_list) max_depth = max(cur_depth, max_depth) alphabet_list[alphabet] = 0 return max_depth for _ in range(R): row = str(input()) board.append(row) count= dfs(0, 0, 1) print(count)
시간복잡도
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
3 6 HFDFFB AJHGDH DGAGEH
6
5 5 IEFCJ FHFKC FFALF HFGCF HMCHH
10