[Programmers] 리틀 프렌즈 사천성

2017 카카오코드 본선

코딩테스트 연습 - 리틀 프렌즈 사천성

---

[DFS + 백트래킹]

문제의 이해도는 어렵지 않은 편이었으나, 출력 형식에 주어진 문구가 마음에 안들었다.

해는 여러가지 일테니, 알파벳 순으로 가장 먼저인 답을 출력하라니... 열심히 풀었건만 저 문장 때문에 코드를 싹 갈아엎었다.

 

다른 사람들은 타일을 깰 수 있는 조건으로 현재 타일에서 수평/수직/왼쪽 위, 아래/오른쪽 위, 아래 타일이 있을 때 이렇게 나누어서 한 것 같다. 나는 그냥 탐색하도록 했다. 예를 들어 현재 타일이 'A'이면 인접한 정점의 값이 '.' 또는 'A'일 때만 탐색할 수 있도록. 이는 별로 중요한 부분이 아니므로 각설하고 문제풀이의 흐름을 살펴본다.

 

1) 입력을 저장

board는 String[]으로 주어지는데, 이를 곧이곧대로 문자열로 저장한다면 열심히 풀어도 낭패를 볼 것이다. 백트래킹 자체가 메모리, 시간을 많이 쓸 수 밖에 없는 알고리즘이므로 문자열 때문에 초과가 날 확률이 높다. 따라서 char[][] 배열에 저장하도록 한다.

 

1-1) board 저장하며 List에 담기

List에 'A' ~ 'Z'인 정점의 좌표와 알파벳을 담는다 (물론 클래스로 만들어서) 이를 담는 이유는, 정렬을 하기 위해서다. 해가 여러 개 일 경우 알파벳 순으로 출력해야하기 때문에 이렇게 했다.

 

1-2) List 정렬하고, visit 초기화

열심히 담은 List의 원소들을 정렬한다.

 

2) 반복문을 돌며 List에서 하나씩 순회 --> DFS 수행 (자세한 것은 코드 참조)

(반복문을 탈출하는 조건 : 더이상 지울 수 없을 때)

 

3) DFS에서 중요하게 봐야할 내용

DFS를 들어왔다면 이제 주의해야할 점은, 방향을 '1회' 밖에 꺾지 못한다는 것이다. 방향은 상하좌우(a: 0, 1, 2, 3)가 있다. 더이상 꺾을 수 없을 때와 꺾을 수 있을 때의 조건문을 잘 사용하면 큰 문제는 없다.

 

4) DFS에서 타일을 지웠다면, map의 값을 '.'으로 만들고 true 반환 --> 결과 문자열에 append

# Code </>

import java.util.ArrayList;
import java.util.List;

class Solution {

    static class Point{
        int y, x;
        char c;

        public Point(int y, int x, char c) {
            this.y = y;
            this.x = x;
            this.c = c;
        }
    }
    static List<Point> list;

    static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
    static char[][] map;
    static boolean[][] visit;
    static int row, col;

    static boolean DFS(char c, int y, int x, int dir, int rotate){

        if(dir != -1 && map[y][x] == c) {
        
            System.out.println(">>> 지워진 타일 : " + map[y][x]);
            
            map[y][x] = '.';
            return true;
        }

        boolean result = false;
        visit[y][x] = true;

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if(ny < 1 || nx < 1 || ny > row || nx > col || visit[ny][nx]) continue;
            if(map[ny][nx] != c && map[ny][nx] != '.') continue;

            //이미 한번 꺾었을 때
            if(rotate >= 1) {
                if (a == dir)
                    result |= DFS(c, ny, nx, a, rotate);
            }
            //아직 꺾지 않았을 때
            else
                result |= DFS(c, ny, nx, a, (a == dir)? rotate : rotate + 1);
        }

        visit[y][x] = false;
        return result;
    }

    public String solution(int m, int n, String[] board) {

        StringBuilder sb = new StringBuilder();
        int cnt = 0;

        list = new ArrayList<>();
        map = new char[101][101];
        row = m;
        col = n;

        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++) {
                map[i][j] = board[i - 1].charAt(j - 1);

                if(map[i][j] >= 'A' && map[i][j] <= 'Z') {
                    list.add(new Point(i, j, map[i][j]));
                    cnt++;
                }
            }

        list.sort((a, b) -> a.c - b.c);
        visit = new boolean[row+1][col+1];

        while(true){
            boolean flag = false;

            for(int a=0; a<list.size(); a++){
                Point p = list.get(a);
                int i = p.y;
                int j = p.x;
                char c = p.c;

                if(c < 'A' || c > 'Z') continue;

                if(!visit[i][j]){
                    boolean remove = DFS(c, i, j, -1, -1);

                    if(remove){
                        flag = true;
                        cnt -= 2;
                        sb.append(c);
                        map[i][j] = '.';
                        list.remove(a);
                        break;
                    }
                }
            }
            if(!flag) break;
        }

        return (cnt == 0)? sb.toString() : "IMPOSSIBLE";
    }
}