[백준] 17300 - 패턴

왜 됬지?라는 생각과 함께 풀었다......

죽자고 예외잡고....hard coding하기 싫어서 이것저것 했는데 자꾸 안되니까 짜증나서 혹시나 하고 제대로 되는거도 hard coding으로 바꿔서 코드가 뭔가 길어졌지만....

결론은 되는걸 올림....ㅂㄷㅂㄷ

안되길래 에이씨.....하고 roll back시켰더니 통과된 희한한 문제였다

1. 간편하게 만들기 위해 1~9까지 적힌 map을 생성

2. L의 크기에 따라 pattern 순서를 입력 받으면서, 중복된 숫자가 있으면 바로 NO를 출력하고 종료

3. arr[0]의 좌표를 시작으로 dfs 탐색을 시작한다

4. 탐색 중, map[y][x]가 순서에 맞지는 않지만, 방문 했던 점이라면 그 진행방향으로 한번 더 이동시키고 dfs를 다시 던져준다.

   방문하지 않았지만, 순서에 맞지 않는 지점이라면 false를 리턴, 모두 순회에 성공한다면 true를 계속 반복해서 return받아 종료시킨다.

5. 그것이 아니라면 한 점에서 갈 수 있는 16개의 점을 모두 탐색하며 위의 과정을 dfs탐색 한다.

#include <iostream>
using namespace std;
 
int map[5][5], arr[12];
bool visit[5][5], check[12];
const int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1, 2, 2, -2, -2, -1, 1, -1, 1 };
const int dy[] = { 0, -1, -1, -1, 0, 1, 1, 1, -1, 1, -1, 1, 2, 2, -2, -2 };
int L;
 
bool dfs(int d, int x, int y, int dir) {
    if (d == L) { return true; }
    if (map[y][x] != arr[d] && !visit[y][x]) { return false; }
    if (map[y][x] != arr[d] && visit[y][x]) {
        x += dx[dir]; y += dy[dir];
        if (x <= 0 || y <= 0 || x > 3 || y > 3) return false;
        return dfs(d, x, y, dir);
    }
    visit[y][x] = true;
    for (int i = 0; i < 16; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx <= 0 || ny <= 0 || nx > 3 || ny > 3) continue;
        if (dfs(d + 1, nx, ny, i)) return true;
    }
    visit[y][x] = false;
    return false;
}
 
int main(void) {
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            map[i][j] = j + (i - 1) * 3;
 
    cin >> L;
 
    for (int i = 0; i < L; i++) {
        cin >> arr[i];
        if (check[arr[i]]) {
            cout << "NO" << '\n';
            return 0;
        }
        check[arr[i]] = true;
    }
 
    int sx, sy;
    if (arr[0] == 1) { sx = 1; sy = 1; }
    else if (arr[0] == 2) { sx = 2; sy = 1; }
    else if (arr[0] == 3) { sx = 3; sy = 1; }
    else if (arr[0] == 4) { sx = 1; sy = 2; }
    else if (arr[0] == 5) { sx = 2; sy = 2; }
    else if (arr[0] == 6) { sx = 3; sy = 2; }
    else if (arr[0] == 7) { sx = 1; sy = 3; }
    else if (arr[0] == 8) { sx = 2; sy = 3; }
    else { sx = 3; sy = 3; }
    if (dfs(0, sx, sy, -1)) { cout << "YES" << '\n'; }
    else { cout << "NO" << '\n'; }
    return 0;
}