일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- JavaScript
- Algorithm
- 따라하면서 배우는 C언어
- BASIC
- 따배씨
- greedy
- 인프런
- Math
- udemy
- C언어
- graph
- Algospot
- server
- php
- sorting
- programmers
- BFS
- 백준
- DP
- BOJ
- Cleancode
- 정수론
- Python
- 종만북
- 생활코딩
- web
- dfs
- 따라하며 배우는 C언어
- C
- String
- Today
- Total
몽상실현개발주의
[BOJ] 1987 / 알파벳 / Python 파이썬 본문
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
[BOJ] 1987 / 알파벳 / Python 파이썬
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
풀이
시간 조건이 굉장히 빠듯하다고 느꼇던 백트레킹 문제였다.
최장거리 경로탐색과 비슷하지만, 알파벳을 기록하는 부분에서 시간초과가 발생하였다.
다른분들의 풀이를 참고하니, dequeue 가 아닌 set 을 이용한 bfs 로 동작시간을 단축 하던가,
알파벳을 숫자로 변화하여 visited 로 처리하였는데 후자의 경우로 풀어보았다.
import sys
input = sys.stdin.readline
R, C = map(int, input().split())
maps = []
for _ in range(R):
maps.append(list(input().rstrip()))
x = y = 0
res = 0
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
visited = [0] * 26
visited[ord(maps[0][0]) - 65] = 1
def DFS(y, x, cnt):
global res, R, C
res = max(res, cnt)
for i in range(4):
Y = y + dy[i]
X = x + dx[i]
if 0 <= Y < R and 0 <= X < C and not visited[ord(maps[Y][X]) - 65]:
visited[ord(maps[Y][X]) - 65] = 1
DFS(Y, X, cnt+1)
visited[ord(maps[Y][X]) - 65] = 0
DFS(y, x, 1)
print(res)
참고 블로그
DFS 풀이
https://it-garden.tistory.com/272
백준알고리즘 - 1987번 알파벳 - 파이썬(Python)
문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한
it-garden.tistory.com
BFS 풀이
[백준/파이썬] 1987 알파벳
https://www.acmicpc.net/problem/1987BFS탐색할 때, 갈 수 있는 여러 개의 길 중에서 끝까지 탐색했을 때 제일 최대값을 구하는 것이다.예를 들어, 3 4CABCDEFGKABC 의 경우에는 다음과 같다. 다만 이때 queue는 중
velog.io
'Algorithm PS > BOJ' 카테고리의 다른 글
[BOJ] 1182 / 부분수열의 합 / Python 파이썬 (0) | 2021.08.09 |
---|---|
[BOJ] 6603 / 로또 / Python 파이썬 (0) | 2021.08.09 |
[BOJ] 2580 / 스도쿠 / Python 파이썬 (0) | 2021.08.05 |
[BOJ] 1759 / 암호 만들기 / Python 파이썬 (0) | 2021.08.04 |
[BOJ] 5014 / 스타트링크 / Python 파이썬 (0) | 2021.08.04 |