티스토리 뷰

알고리즘/백준

[BAEKJOON]1987 알파벳- Python

응애~ 개발자 2023. 2. 20. 11:22
728x90
반응형

  • 알고리즘 분류:백트레킹, DFS, 시물레이션
  • 난이도: Gol4
  • 문제내용:
    • 세로 R, 가로 C의 알파벳 보드가 있다.
    • (1, 1)부터 시작해서 상하좌우 이동할때 같은 알파벳 2번 지날 갈수  가 없다.
    • 최대 이동할수 있는 횟수를 구해라.
  • 사이트: https://www.acmicpc.net/problem/1987
 

1987번: 알파벳

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으

www.acmicpc.net

문제풀이

   이번에는 문제는 백트레킹 또는 DFS 두가지 방법으로 풀수가 있다. 백트레킹 이나 DFS(깊이 우선 탐색)에 대한 설명은 아래 사이트에서 확인 해보면된다.

 

[알고리즘 이론] 깊이 우선 탐색(DFS)

이론 이번에 볼 자료구조는 깊이 우선 탐색(DFS)이다. 깊이 우선 탐색은 영어로 Depth First Search이고 줄어서 DFS라고 많이 부른다. 그래프 탐색 알고리즘 중 하나인데 그래프 말고도 트리에서도 적용

jih3508.tistory.com

 

백트래킹 - 나무위키

일반적으로 특정 퀘스트나 스토리를 클리어하기 위해 게임을 진행한 뒤, 자동으로 초기 지점으로 돌아오는 기능 등이 없어 왔던 길을 플레이어가 직접 캐릭터를 조정해 처음부터 다시 돌아와야

namu.wiki

  이번 문제는 골드 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
링크
«   2025/01   »
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
글 보관함