김호쭈
DevForYou
김호쭈
전체 방문자
오늘
어제
  • 분류 전체보기 (321)
    • • 데이터베이스(DB) (9)
      • __SQL__ (9)
    • •알고리즘(Algorithm ) (117)
      • 문제풀이 (99)
      • 스터디 (14)
      • 알고리즘 팁 (4)
    • •Compter Science (57)
      • Operating System (25)
      • Computer Network (1)
      • Computer Vision (16)
      • Artificial Intelligence (14)
      • Software Technology (1)
    • • 독서 (36)
      • Design Pattern (24)
      • 객체지향의 사실과 오해 (1)
      • Object Oriented Software En.. (11)
    • • 개발 (26)
      • React (3)
      • node.js (6)
      • Django (11)
      • Spring boot (6)
    • • 개발Tip (4)
      • GitHub (0)
    • •프로젝트 (2)
      • 물물 (2)
    • •App (54)
      • 안드로이드 with Kotlin (50)
      • 코틀린(Kotiln) (4)
    • •회고 (8)
    • •취준일기 (3)
    • • 기타 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • GitHubDesktop
  • ㄱ
  • 로컬저장소
  • Remote저장소
  • 깃허브데스크탑
  • KMU_WINK
  • 원격저장소
  • local저장소

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
김호쭈

DevForYou

•알고리즘(Algorithm )/문제풀이

[백준1987&파이썬] DFS와 백트래킹을 이용하여 조건에 맞는 값을 구하자

2023. 4. 13. 22:56

# 문제

백준 1987 알파벳 파이썬 풀이

 

1987번: 알파벳

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

www.acmicpc.net

# 코드

## 성공한 풀이

import copy
import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

dirs = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

# visit = [[True] * C for _ in range(R)] 방문처리가 필요하지 않음

board = list()
max_cnt = 0
for _ in range(R):
  line = list(sys.stdin.readline().strip())
  board.append(line)

# 방문했던 알파벳을 어떻게 관리할 것인가?
# 사용알파벳 관리
# print( ord('Z') - ord('A')) # 0 ~ 25
used = [False] * 26


def dfs(r, c, cnt):
  global max_cnt
  max_cnt = max(cnt, max_cnt)
  # print(f"({r},{c},{cnt})")

  for dir in dirs:
    next = (r + dir[0], c + dir[1])

    if 0 <= next[0] < R and 0 <= next[1] < C:
      if used[ord(board[next[0]][next[1]]) - ord('A')] == False:  # 사용하지 않았던 알파벳이라면
        used[ord(board[next[0]][next[1]]) - ord('A')] = True
        dfs(next[0], next[1], cnt + 1)
        used[ord(board[next[0]][next[1]]) - ord('A')] = False

used[ord(board[0][0]) - ord('A')] = True # 초기 시작점은 항상 사용됨
dfs(0, 0, 1)
print(max_cnt)

 

## 실패한 풀이 ( 시간 초과 )

import copy
import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

dirs = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

# visit = [[True] * C for _ in range(R)] 방문처리가 필요하지 않음

board = list()
max_cnt = 0
for _ in range(R):
  line = list(sys.stdin.readline().strip())
  board.append(line)


# ##### ------ 시간초과 풀이 ------ #####
# stk = deque()
# stk.append((0, 0, [],1))  # ( row, col, 방문했던 알파벳 )
#
# while len(stk) != 0 :
#   cur = stk.pop()
#   max_cnt = max(max_cnt,cur[3])
#
#   for dir in dirs :
#     next_list = copy.deepcopy(cur[2])
#     next_list.append(board[cur[0]][cur[1]])
#     next = ( cur[0] + dir[0], cur[1] + dir[1], next_list, cur[3] + 1 )
#
#     if 0 <= next[0] < R and 0<= next[1] < C : # 범위 체크
#         if board[next[0]][next[1]] not in next[2] : # 중복되는 알파벳이 없다면
#           stk.append(next) # 스택에 넣어주고
#
#
# print(max_cnt)
# ##### ------------------------ #####

 

# 풀이

## 이미 지났던 알파벳을 판단하는 방법

### 시간초과로 틀렸던 풀이

  • bfs에서 프로시져방법을 이용해서 이전까지의 상태를 계속 이어오는 방법을 적용하여 DFS로 풀었다.
  • 스택에 넣어주는 노드(단위)에서 현재를 뽑으면 3번째 인자에 담긴 리스트에 여기까지 오면서 밟았던 알파벳을 저장시켰다
  • 그러나 deppcopy하는 과정과 거기 안에 해당 알파벳이 있는지 탐색하는 과정에서 시간이 많이 쓰여 시간초과가 난걸로 예상한다.

### 백트래킹과 사용한 알파벳을 GLOBAL에서 관리하기

  • 백트래킹을 이용해 막혔을때 원래 상태로 되돌리는게 쉽게 가능하다. (아래 코드와 같이)
used[ord(board[next[0]][next[1]]) - ord('A')] = True
dfs(next[0], next[1], cnt + 1)
used[ord(board[next[0]][next[1]]) - ord('A')] = False
  • 사용한 알파벳은 글로벌로 하고 한개만 사용해서 관리 할 수 있다. max(출력해야할 값)은 별도로 계속 최신화를 시킨다.
  • 알파벳 대문자 'A' ~ 'Z' 까지 총 26개의 문자를 인덱싱하기 위해 아스키코드( ord ) 를 사용한다.
ord(board[next[0]][next[1]]) - ord('A')
  • 이렇게 하면 'A'는 0 ... 'Z'는 25의 인덱스를 가지게 되고 해당 인덱스가 True/False인지에 따라서 다음 방문 여부를 결정한다.

## 방문처리는 필요하지 않았다. 

  • 반복문으로 순서대로 돌고, 알파벳 사용 여부에 따라서 다음으로 이동이 가능한지를 판단한다.
  • 이번에 그 방향으로 진출했다면 다음상황에 그 방향으로 어차피 진출 할 수 없다. (반복문에 의해서)

## 첫 시작점을 잊지 말자

  • 다풀고 첫 시작점 방문처리를 안해서 오답이 나왔다. 

 

# 참고

  • 백트래킹은 DFS도중 조건을 확인해 더이상 탐색하지 않아도 된다면 탐색하지 않는 것을 의미한다.
  • 백트래킹은 일반적으로 재귀의 형태로 작성되고, 재귀가 종료되는 시점에서 다시 원래  상태로 복구 시키기 용이하고 깔끔하다.
저작자표시 (새창열림)

'•알고리즘(Algorithm ) > 문제풀이' 카테고리의 다른 글

[백준11725&파이썬] BFS와 DFS에서 그래프 인접리스트의 활용  (1) 2023.04.15
[백준1520&파이썬] DFS에 메모이제이션을 곁들여서 시간초과를 해결하자  (1) 2023.04.15
[백준2573&파이썬] BFS를 활용할때는 단계적으로 잘 나누어 풀자  (0) 2023.04.11
[백준2206&파이썬] BFS에서 이동상태가 분리된다면 방문 확인도 분리시켜야 한다.  (0) 2023.04.10
[백준6593&파이썬] BFS로 3차원 공간을 탐색할 수 있다.  (0) 2023.04.09
    '•알고리즘(Algorithm )/문제풀이' 카테고리의 다른 글
    • [백준11725&파이썬] BFS와 DFS에서 그래프 인접리스트의 활용
    • [백준1520&파이썬] DFS에 메모이제이션을 곁들여서 시간초과를 해결하자
    • [백준2573&파이썬] BFS를 활용할때는 단계적으로 잘 나누어 풀자
    • [백준2206&파이썬] BFS에서 이동상태가 분리된다면 방문 확인도 분리시켜야 한다.
    김호쭈
    김호쭈
    공부하고 정리하고 기록하기

    티스토리툴바