[ Baekjoon - 11/10 ] - 1987번: 알파벳

• 문제 링크 : https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

• 소요 시간 : 2시간

알파벳 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

82419

26408

16163

29.046%

문제

세로 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

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 256MB
   • 문제
     
     • R x C의 지도(1≤R,C≤20)
     • (1,1)에서 출발해서 갈 수 있을때까지 이동 가능하다.
     • 갈 수 있는 조건은 상하좌우 좌표가 각각 맵안이고, 나아갈 좌표의 알파벳이 이때까지 지나온 알파벳이 아닐 경우이다.
     • 최대 몇칸까지 갈수있는지 출력하는 문제이다.
   • 이해
     • 문제 이해는 어렵지 않았지만, 어떻게 풀어나가야할지를 오래 고민했다..
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 입력 양식에 따라 조건과 함께 적어보았고, 간단히 그려보았다. 
   • 문제 이해는 간단히 끝냈지만 어떤식으로 접근해야할지 감을 잡기위해 입출력예제를 직접 그려본 뒤 케이스를 따져보았다.

   • 

   • 그런데 케이스들이.. 너무 단순한 형태였어서 규칙을 찾기란 조금 난해해보였다.. 정말 문제에서 준 조건말고는 얻을게 없었던 케이스들 ㅠ
3. 문제를 어떻게 해결할 것인가
   
   • 1st 접근 - 완탐이 될것인가...? DFS)
     • 알파벳은 26개이고 이동가능한 방법은 상하좌우 4개이므로 O(4^26)정도의 시간복잡도를 가진다고 생각해보면, 거의 10억이지만... 지나왔던 길이나 알파벳은은 다시 안가도 되므로 좀더 적은 시간에 수행가능하다고 추측해볼 수 있다. 
     • DFS로 풀 경우, 위 조건들만 잘 지켜주면서 구현하면 크게 어렵지는 않았다.
     • 자바로는 성공했지만, 파이썬으로는 시간초과가 발생했다.. 여러번 최적화를 시도했지만 불가능해보이기도..
   • 2nd 접근 - BFS)
     • 규칙을 찾을 수 있는 문제가 아닌것같아서 결국 완탐이라 생각했고... DFS보다 시간복잡도상으로 우위인 BFS를 활용해보고자 했다.
     • BFS로 하면 지금 현재 방문을 어디까지했는지가 통일되지 않아서 함수 호출시 같이 가져올 수 있어야하는데, 맵 200칸에 대해 현재 방문한 좌표리스트를 들고있게 하기란 256MB 메모리가 안타까워보였고, 그 리스트에 현재 좌표가 속하는지를 빠르게 비교하기에도 난해해보였다.
     • 질문하기에서 솔루션을 찾던 중 set을 이용하면 빠르게 가능하다 해서 시도해보았고 그 덕에 Python3으로 제출할 수 있었다.
4. 위 계획을 검증
   • 완탐이므로 생략
5. 계획 수행 (실제코드 작성)
   1. Java 11

      1. import java.util.*;
         import java.io.*;
         
         public class Main {
             static int R, C, ans=0;
             static int[][] map;
             static boolean[] vis = new boolean[26];
             static int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, -1, 1 };
         
             public static void DFS(int x, int y, int count) {
                 if (vis[map[x][y]]) {
                     ans = Math.max(ans, count);
                     return;
                 } else {
                     vis[map[x][y]] = true;
                     for (int r = 0; r < 4; r++) {
                         int nx = x + dx[r];
                         int ny = y + dy[r];
         
                         if (0<=nx && nx<R && 0<=ny && ny<C) {
                             DFS(nx, ny, count + 1);
                         }
                     }
                     vis[map[x][y]] = false;
                 }
             }
         
             public static void main(String[] args) throws IOException {
                 //System.setIn(new FileInputStream("src/input.txt"));
         
                 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
                 StringTokenizer st = new StringTokenizer(br.readLine());
                 R = Integer.parseInt(st.nextToken());
                 C = Integer.parseInt(st.nextToken());
                 map = new int[R][C];
                 for (int r = 0; r < R; r++) {
                     String str = br.readLine();
                     for (int c = 0; c < C; c++) {
                         map[r][c] = str.charAt(c) - 'A';
                     }
                 }
         
                 DFS(0, 0, 0);
                 bw.write(ans+"\n");
                 bw.flush();
             }
         }

   2. PyPy3 - Python으로는 불가했지만 PyPy로는 맞았던 코드

      1. import sys
         input = sys.stdin.readline
         
         R, C = map(int, input().split())
         board = [list(input().rstrip()) for _ in range(R)]
         vis = [False for _ in range(26)]
         dx = [-1,1,0,0]
         dy = [0,0,-1,1]
         ans = 0
         
         def DFS(x, y, cnt):
             global ans
             idx = ord(board[x][y]) - 65
             # 이미 방문한 글자라면 - 글자수 기록(최대만)
             if vis[idx]:
                 ans = max(ans, cnt)
                 return
             # DFS - 맵안이라면 나아가기
             else:
                 vis[idx] = True
                 for r in range(4):
                     nx = x + dx[r]
                     ny = y + dy[r]
                     if 0<=nx<R and 0<=ny<C:
                         DFS(nx,ny,cnt+1)
                 vis[idx] = False
         
         if __name__ == '__main__':
             DFS(0,0,0)
             print(ans)

   3. Python 3

      1. import sys
         # sys.stdin = open("input.txt")
         input = sys.stdin.readline
         
         def BFS(xyAlpha):
             q = {xyAlpha}
             cnt = 1
             while q:
                 # 1. 큐에서 꺼냄
                 x, y, visAlpha = q.pop()
                 # 2. 연결
                 for i in range(4):
                     # 3. 갈수있 - 최대 한도 X, 맵안, 지나온 알파벳 X
                     if cnt >= 26:
                         return cnt
                     nx, ny = x + dxy[i][0], y + dxy[i][1]
                     if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in visAlpha:
                         # 4. 큐에넣음
                         q.add((nx, ny, visAlpha + board[nx][ny]))
                         # 5. 체크인
                         cnt = max(cnt, len(visAlpha) + 1)
             return cnt
         
         if __name__ == "__main__":
             R, C = map(int, input().split())
             board = [list(input().strip()) for _ in range(R)]
             dxy = {0: (-1, 0), 1: (1, 0), 2: (0, -1), 3: (0, 1)}
             print(BFS((0, 0, board[0][0])))

 

• 결과

런타임 에러는 A가 아스키코드상으로 65인데 64라고 착각해서 얻은 결과이다 ㅋㅋ......