[BOJ] 1987.알파벳(DFS,백트래킹).java

 

 

#. Problem

https://www.acmicpc.net/problem/1987

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

 

#. Solve

 

4방향으로 탐색을 하는데,

지나온 알파벳 정보를 들고 탐색을 해보자.

 

탐색 도중에 이미 지나온 알파벳이 적힌 칸이 있다면 더이상 가지 않는다.

 

#. Code

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ1987 {      static int R, C, res;    static boolean[] alpa;    static char[][] map;    static int[] dr = { -1, 0, 1, 0 }, dc = { 0, -1, 0, 1 };      public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       StringTokenizer st = new StringTokenizer(br.readLine());         R = Integer.parseInt(st.nextToken());       C = Integer.parseInt(st.nextToken());       map = new char[R][];       for (int i = 0; i < R; i++)          map[i] = br.readLine().toCharArray();         alpa = new boolean[26];       // 시작 지점       alpa[map[0][0] - 'A'] = true;       move(0, 0, 1);              System.out.println(res);    }      private static void move(int r, int c, int cnt) {        // 모든 알파벳을 다 모았을 경우 최대 칸이므로 더이상 볼 필요가 없음        if(res == 26) return;           // 4방 탐색       int rr, cc;       for (int d = 0; d < 4; d++) {          rr = r + dr[d];          cc = c + dc[d];                    // 범위를 벗어날 경우 pass          if(rr < 0 || cc < 0 || rr >= R || cc >= C) continue;          // 알파벳이 이미 체크되어있다면 pass          if(alpa[map[rr][cc] - 'A']) continue;            // 현재 알파벳 체크          alpa[map[rr][cc] - 'A'] = true;          // 갈 수 있는 곳이라면 가보자!          move(rr, cc, cnt + 1);          // 현재 알파벳 체크 해제          alpa[map[rr][cc] - 'A'] = false;       }       // 사방으로 갈 길이 없다면 최대 칸 수 갱신       res = Math.max(res, cnt);    }   } Colored by Color Scripter

cs

 

 

 

 

#. Code_v2 (Using Bitmask)

 

알파벳 체크를 비트마스크를 사용해서 해결해보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ1987_v2 {
 
    static int R, C, res;
    static char[][] map;
    static int[] dr = { -1, 0, 1, 0 }, dc = { 0, -1, 0, 1 };
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][];
        for (int i = 0; i < R; i++)
            map[i] = br.readLine().toCharArray();
 
        move(0, 0, 0 | (1 << map[0][0] - 'A'), 1);
 
        System.out.println(res);
    }
 
    private static void move(int r, int c, int alpa, int cnt) {
        // 모든 알파벳을 다 모았을 경우 최대 칸이므로 더이상 볼 필요가 없음
        if (res == 26) return;
        // 최대 칸 수 갱신
        res = Math.max(res, cnt);
        
        // 4방 탐색
        int rr, cc;
        for (int d = 0; d < 4; d++) {
            rr = r + dr[d];
            cc = c + dc[d];
 
            // 범위를 벗어날 경우 pass
            if (rr < 0 || cc < 0 || rr >= R || cc >= C) continue;
            // 이미 획득한 알파벳이 있다면 pass
            if ((alpa & (1 << map[rr][cc] - 'A')) != 0) continue;
            // 갈 수 있는 곳이라면 가보자!
            move(rr, cc, alpa | (1 << map[rr][cc] - 'A'), cnt + 1);
        }
        
    }
 
}