[프로그래머스] 리틀 프렌즈 사천성

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/1836#

문제 풀이

• BFS로 풀이하였다.
• 시간복잡도 자체는 타이트하지 않아서 쉽게 생각했지만 구현이 조금은 복잡해서 잔실수가 많이 나왔다.
• 기억나는 실수들
  - 카드를 모두 매칭시키지 않으면 불가능 리턴
  - 알파벳 순으로 빠른 알파벳부터 BFS를 진행하는데 카드 매칭이 되면 다시 처음 알파벳부터 반복필요
  - 방문 탐색시 방향값 추가해줘야함 (chk[x좌표][y좌표][방향])
  - 카드 매칭시에 시작, 끝지점 모두 빈 칸으로 만들어 줘야함.
  - 진행 방향은 왼쪽 꺾기, 정방향, 오른쪽 꺾기 3방향씩 탐색

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, M;
    public int[][] map;
    public Point[] start = new Point[26];
    public int[] dx = {0,1,0,-1};
    public int[] dy = {1,0,-1,0};

    public class Point {
        int x, y, d, k;

        public Point(int x, int y, int d, int k) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.k = k;
        }
    }

    public int calDir(int d, int diff) {
        int res = d + diff;
        if (res == 4) return 0;
        else if (res == -1) return 3;
        else return res;
    }

    public String solution(int m, int n, String[] board) {
        //초기화
        int resCnt = 0;
        N = m;
        M = n;
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                char card = board[i].charAt(j);
                if (card >= 'A' && card <= 'Z') {
                    if (start[card - 'A'] == null) {
                        resCnt++;
                        start[card - 'A'] = new Point(i, j, 0, 0);
                    }
                    map[i][j] = card - 'A';
                } else if (card == '.')
                    map[i][j] = -1;         //빈칸
                else
                    map[i][j] = -2;         //벽
            }
        }

        Queue<Point> q = new ArrayDeque<>();
        StringBuilder result = new StringBuilder();
        while(true) {
            boolean flag = true;
            //모든 가능 카드에 대해 반복
            for (int c = 0; c < 26; c++) {
                if (!flag) break;
                if (start[c] == null) continue;
                q.clear();
                boolean[][][] chk = new boolean[N][M][4];

                //bfs 진행
                for (int d = 0; d < 4; d++) {
                    int X = start[c].x + dx[d];
                    int Y = start[c].y + dy[d];
                    if (X < 0 || Y < 0 || X >= N || Y >= M || (map[X][Y] != -1 && map[X][Y] != c)) continue;
                    chk[X][Y][d] = true;
                    q.add(new Point(X, Y, d, 0));
                }

                while(!q.isEmpty()) {
                    Point cur = q.poll();
                    //결과 바꿔주기
                    //마지막 지점이 시작 지점과 같을 경우
                    if (map[cur.x][cur.y] == c) {
                        //시작, 끝 빈 칸 만들어주기
                        map[start[c].x][start[c].y] = -1;
                        map[cur.x][cur.y] = -1;
                        //후보에서 제외
                        start[c] = null;
                        //결과에 더해줌
                        result.append((char)(c + 'A'));
                        //flag 변화
                        flag = false;
                        break;
                    }
                    //좌로 꺾기, 정방향, 우로 꺾기
                    for (int dd = -1; dd <= 1; dd++) {
                        //횟수 소진되었으면 더이상 꺾기 불가
                        if (cur.k == 1 && (dd == -1 || dd == 1)) continue;
                        int D = calDir(cur.d, dd);
                        int X = cur.x + dx[D];
                        int Y = cur.y + dy[D];
                        if (X < 0 || Y < 0 || X >= N || Y >= M || (map[X][Y] != -1 && map[X][Y] != c)) continue;
                        if (chk[X][Y][D]) continue;
                        chk[X][Y][D] = true;
                        if (cur.k == 1) q.add(new Point(X, Y, D, 1));
                        else q.add(new Point(X, Y, D, cur.d == D ? 0 : 1));
                    }
                }
            }
            if (flag) break;
        }
        if (result.length() != resCnt) return "IMPOSSIBLE";
        else return result.toString();
    }
}