leah

my dev_log

0%

BOJ 1987

Posted on In ,

Input

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)

둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

1
2
3
4
5
import sys
input = sys.stdin.readline

r, c = map(int, input().split())
s = [list(map(lambda x: ord(x) - 65, input().strip())) for _ in range(r)]

ㅋㅋㅋ 이거… 이거 만만하게 보면 안 된다. 이번 문제는 알고리즘도, 코드도 쉬운데 입력 처리 때문에 1시간 날려먹음 ◡̈ 무조건! string이 아니라 ASCII 코드 이용해서 int로 변환해 저장해야 한다. ㅎㅎ

DFS

처음에는 BFS로 시도했으나.. DFS가 더 편할 것 같다는 판단에 수정했다. 내가 놓쳤던 부분이자 배운 부분은

  • dfs 호출 전후로 스택과 같이 push, pop 구현하기

이다.

코드는 쉬움.

  • 알파벳 방문이기 때문에 직전 문제처럼 알파벳 배열을 생성해서 방문 체크 하면 됨.

    1
    2
    3
    dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    visited = [False]*(ord('a') - ord('A'))
    visited[s[0][0]] = True

  • 최대값 출력이기 때문에 max 값 저장용으로 global 변수 를 이용한다.

    1
    2
    3
    4
    5
    6
    7
    8
    ret = 1
    .
    .
    .
      global ret

      if cnt > ret:
        ret = cnt

  • 이 외에는 여느 때와 다름 없이, 범위 & 방문 체크. 여기서 조건 만족 시 바로 dfs 호출이 아니라 pop, push를 구현해야 한다! dfs 호출 전 push, dfs 호출이 끝나면 pop 해서 깊이 우선 탐색을 시행한다.

    1
    2
    3
    4
    5
    6
    7
    8
    for d in dir:
      nx = i + d[0]
      ny = j + d[1]
      
      if 0 <= nx < r and 0 <= ny < c and not visited[s[nx][ny]]:
        visited[s[nx][ny]] = True
        dfs(nx, ny, cnt + 1)
        visited[s[nx][ny]] = False

Output

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

1
2
dfs(0, 0, 1)
print(ret)