알파벳 [JAVA] (백준 1987)

 

문제

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

1987번: 알파벳

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	256MB	49942	15751	9613	29.144%

문제

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

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

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

입력

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

출력

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

 

풀이

처음에는 좌표와, String형 문장 (내가 이동한 경로)를 가지고 있는 클래스를 선언하여 BFS로 구현하고자 하였다.

하지만 메모리 초과 문제가 발생하였는데, 큐에 중복된 좌표가 들어가는 것을 막는게 힘들었기 때문이다.

q.contains()를 사용해봤는데, 시간이 어마어마하게 걸렸다.

다른 언어였으면 편하게 set을 사용하겠지만, JAVA에서는 set이 원하는 값만 뽑아내기가 쉽지 않아서 불가능했다.

그래서 DFS로 선회해서 풀었다.

재귀를 통해 모든 경로에 대해 탐색해보면서 HashMap에 앞으로 갈 좌표가 있는지 체크하였다.

재귀 호출 이후에 초기화 하는 부분을 까먹지 않도록 유의해야겠다.

너무 시간이 많이 나와서 ASCII로 char를 변경도 해 보았는데, 약간의 효과가 있었다.

 

코드

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int R;
    static int N;
    static int answer;

    static int[][] map;

    static HashMap<Integer, Integer> visited = new HashMap<Integer,Integer>();
    static int[] xMove = {0,0,1,-1};
    static int[] yMove = {1,-1,0,0};


   public static void main(String[] args) throws IOException{
      StringTokenizer st;
      BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));

      st = new StringTokenizer(br.readLine());
      R = Integer.parseInt(st.nextToken());
      N = Integer.parseInt(st.nextToken());

      map = new int[R][N];
      char[] a;

      for(int y=0; y<R; y++) {
          st = new StringTokenizer(br.readLine());
          a = st.nextToken().toCharArray();

          for(int x=0; x<N; x++) {
              map[y][x] = Character.getNumericValue(a[x]);
          }
      }
      DFS(0,0,1);
      System.out.println(answer);
   }

   public static void DFS(int y, int x, int round) {
       int num = map[y][x];
       visited.put(num, num);

       answer = Math.max(round, answer);
       int currY, currX;

       for(int i=0; i<4; i++) {
           currY = y+yMove[i];
           currX = x+xMove[i];

           if(currY < 0  || currY >= R ||currX < 0 || currX >= N) continue;

           if(!visited.containsKey(map[currY][currX])) {
               DFS(currY, currX, round+1);
           }
       }
       visited.remove(num);
   }
}

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!