1954 달팽이 숫자

달팽이 숫자 URL

내 풀이

import java.io.*;
import java.util.*;

public class SW1954 {
    static boolean[][] visited;
    static int[][] graph;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            int N = Integer.parseInt(br.readLine());
            visited = new boolean[N][N];
            graph = new int[N][N];

            graph[0][0] = 1;
            dfs(0, 0, 2, N);
            System.out.println(Arrays.deepToString(graph));
        }
    }

    public static void dfs(int a, int b, int cnt, int N) {
        visited[a][b] = true;

        for (int i = 0; i < 4; i++) {
            int nx = a + dx[i];
            int ny = b + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                if (visited[nx][ny] == false) {
                    graph[nx][ny] = cnt;
                    dfs(nx, ny, cnt+= 1, N);
                }
            }
        }
    }
}

문제점

백준에서 비슷한 문제를 본 적 있어서 DFS로 풀면 되겠다고 생각했다.
동 -> 남 -> 서 -> 북 방향으로 회전하면서 cnt를 하나를 채워 나가는 방식으로 풀이하였는데
3일 경우는 예시랑 답이 일치해서 맞춘건가 생각했는데 4일 경우 다르게 나왔다.

결과

123
456
789

1  2  3  4
16 15 14 5
11 12 13 6
10 9  8  7

이런식으로 나왔다.
문제는 벽에 닿을 경우만 회전을 해야되는데 내 경우는 0번째인 동쪽부터 회전이 되도록 반복해서 동쪽으로 회전이 가능한 경우 위로 쭉 가지 않고 회전해 버렸다.
이 문제를 고민해 봤지만 시간이 너무 오래걸려 다른 풀이를 봤다..

Solution

import java.io.*;

public class SW1954 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        for (int t = 1; t <= T; t++) {
            int N = Integer.parseInt(br.readLine());

            int[][] graph = new int[N][N];

            System.out.println("#" + t);
            int x = 0, y = 0;
            int idx = 0;
            for (int i = 1; i <= N*N; i++) {
                graph[x][y] = i;
                int nx = x + dx[idx];
                int ny = y + dy[idx];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N || graph[nx][ny] != 0) {
                    idx = (idx+1) % 4;
                }
                x += dx[idx];
                y += dy[idx];
            }
            for (int i = 0; i < N; i++) {
                for (int j : graph[i]) {
                    System.out.print(j + " ");
                }
                System.out.println();
            }
        }
    }
}

배운점

먼저 DFS를 사용하지 않아도 풀 수 있는 문제인것을 보고 아직 문제 파악이 부족하다고 생각했다.
이 문제는 조건과 방향전환이 전부이다.

풀이

1. 동 -> 남 -> 서 -> 북 순서로 회전할 수 있도록 dx, dy 배열을 설정
2. 벽에 닿거나 값이 0인경우 회전한다.
3. 회전은 idx = (idx+1) % 4 식을 적용하면 1, 2, 3, 0, 1... 순서로 회전이 된다.

바로 직전에 풀었던 문제와 유사한데 너무 복잡하게 생각했던것 같다.