[boj] 1987. 알파벳

Category	ps/브루트 포스
Tag	브루트 포스
Tags
난이도	골드 4
발행 여부
사이트	boj
실수 유형
이해	완벽히 이해
최종 편집 일시	@2021년 11월 30일 오후 10:55
푼 날짜	@2021년 11월 30일 오후 10:10

문제 해설 및 주의사항

원문

주의사항

풀이

내 풀이 코드 (통과)

풀이 코드 (시간초과)

퇴고

문제 해설 및 주의사항

원문

• 열기

  문제

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

  말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

  좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

  입력

  첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

  출력

  첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

  예제 입력 1

  2 4
  CAAB
  ADCB
  

  예제 출력 1

  3
  

  예제 입력 2

  3 6
  HFDFFB
  AJHGDH
  DGAGEH
  

  예제 출력 2

  6
  

  예제 입력 3

  5 5
  IEFCJ
  FHFKC
  FFALF
  HFGCF
  HMCHH
  

  예제 출력 3

  10

주의사항

---

풀이

내 풀이 코드 (통과)

import sys

r,c = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(r)]
is_used = [False for _ in range(26)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]
def recursion(y: int, x: int)-> None:
  ans = 0
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    # 범위 체크
    if ny >= 0 and ny < r and nx >= 0 and nx < c:
      if is_used[ord(board[ny][nx]) - ord('A')] == False:
        is_used[ord(board[ny][nx]) - ord('A')] = True
        tmp = recursion(ny, nx)
        if ans < tmp:
          ans = tmp
        is_used[ord(board[ny][nx]) - ord('A')] = False
  return ans + 1

is_used[ord(board[0][0]) - ord('A')] = True
print(recursion(0,0))

풀이 코드 (시간초과)

import sys

r,c = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(r)]
is_used = [False for _ in range(26)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]
ans = 0
def recursion(y: int, x: int, count: int)-> None:
  global ans
  # 정답처리
  if count > ans:
    ans = count

  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    
    # 범위 체크
    if ny >= 0 and ny < r and nx >= 0 and nx < c:
      if is_used[ord(board[ny][nx]) - ord('A')] == False:
        is_used[ord(board[ny][nx]) - ord('A')] = True
        recursion(ny, nx, count + 1)
        is_used[ord(board[ny][nx]) - ord('A')] = False

is_used[ord(board[0][0]) - ord('A')] = True
recursion(0,0,1)
print(ans)

---

퇴고

• python3 보다 pypy 로 제출하는 것이 더 합당한 결과를 내줄 때가 많다.
  • 파이썬 주의사항 참고