티스토리 뷰
728x90
반응형
- 알고리즘 분류:백트레킹, DFS, 시물레이션
- 난이도: Gol4
- 문제내용:
- 세로 R, 가로 C의 알파벳 보드가 있다.
- (1, 1)부터 시작해서 상하좌우 이동할때 같은 알파벳 2번 지날 갈수 가 없다.
- 최대 이동할수 있는 횟수를 구해라.
- 사이트: https://www.acmicpc.net/problem/1987
문제풀이
이번에는 문제는 백트레킹 또는 DFS 두가지 방법으로 풀수가 있다. 백트레킹 이나 DFS(깊이 우선 탐색)에 대한 설명은 아래 사이트에서 확인 해보면된다.
이번 문제는 골드 4이지만 푸는 방법은 간단하다. 상하좌우로 방문할때 마다 코드를 좌표와 알파벳 저장해서 이전 경로에 좌표와 알파벳이 포함 되어있지 않으면 저장을 하면서 최대길이를 저장하기만 하면되기 때문에 생각만 하면 쉽게 풀수 있다고 생각한다. DFS, 백트레킹에 대한 기본적인것만 알면 문제 풀기가 쉽기 때문에 자세한 설명은 생략 한다.
Code
백트레킹
백트레킹은 시간 복잡도가 다른 알고리즘보다 길어서 pypy로 제출해야 통과가 된다. 그리고 리스트나 문자열에 저장하지 않고 set을 사용한 이유는 리스트나 문자열 포함 되어있는지 확인하는데 O(N)이 걸리지만 Set을 사용하면 O(1)이 되기 때문이다.
import sys
input = sys.stdin.readline
# 좌표
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def alpabet(x, y, road):
global count
for i in range(4):
fx, fy = x + dx[i], y + dy[i]
# 알파벳 포함 되어 있지 않으면 이동하면서 알파벳을 저장한다.
if 0 <= fx < R and 0 <= fy < C and board[fx][fy] not in road:
road.add(board[fx][fy])
alpabet(fx, fy, road)
road.remove(board[fx][fy])
# 최대 이동 거리를 저장한다.
count = max(count, len(road))
R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]
count = 0
alpabet(0, 0, set({board[0][0]}))
print(count)
DFS
import sys
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def alpabet(x, y):
count = 0
# 중복이 없어야 하기 때문에 set을 사용한다.
queue = set([(x, y, board[x][y])])
while queue:
nx, ny, path = queue.pop()
count = max(count, len(path))
for i in range(4):
fx, fy = nx + dx[i], ny + dy[i]
# 이전 알파벳이 있는지 확인한다.
if 0 <= fx < R and 0 <= fy < C and board[fx][fy] not in path:
queue.add((fx, fy , path + board[fx][fy]))
return count
R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]
print(alpabet(0, 0))
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[BAEKJOON]1759 암호 만들기 - python (0) | 2023.02.22 |
---|---|
[BAEKJOON]1890 점프 (0) | 2023.02.21 |
[BAEKJOON]5014 스타트링크 (0) | 2023.02.17 |
[BAEKJOON]2583 영역 구하기 (0) | 2023.02.16 |
[BAEKJOON]1309 동물원 (0) | 2023.02.14 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 조합
- 배열
- 파이썬
- BFS
- 알고리즘
- Python
- 그래프
- 문자열
- DFS
- 재귀호출
- spring-boot
- 동적계획법
- 자바
- 구현
- LeetCode
- 동적 계획법
- Greedy
- level2
- BaekJoon
- DP
- 넓이 우선 탐색
- JSCODE
- 누적합
- Programmerse
- 수학
- 백준
- 그리디
- 이론
- 백트레킹
- java
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 29 | 30 | 31 |
글 보관함