1954. 달팽이 숫자 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공 (31분)

아이디어

우선 처음 든 생각은 DFS로 한 방향으로 숫자를 늘리면서 배열에 넣어주고
막히거나 이미 방문한 곳이라면 우 -> 하 -> 좌 -> 상 -> 우로 방향전환을 해주려고 생각했다.

만약 현재 방향대로 갈 수 있다면 같은 방향으로 이동시켜주고
만약 현재 방향대로 갈 수 없다면 다른 조건은 동일하게 유효성검사를 해주고
방향은 (dir+1)%4로 방향으로 변경한다.

정답 코드

package codingTest;
import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int [][] map;
    static boolean [] checked;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int t= 1; t<=T; t++) {
            N = Integer.parseInt(br.readLine());
            map = new int [N][N];
            checked = new boolean[N*N+1];
            sb.append("#"+t+"\n");
            checked[1] = true;
            makeSnail(0,0, 1, 0);
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    sb.append(map[i][j]+" ");
                }
                sb.append("\n");
            }
        }
        sb.setLength(sb.length()-1);
        System.out.print(sb);
    }
    static int [] dx = {0, 1, 0, -1};
    static int [] dy = {1, 0, -1, 0};
    static void makeSnail(int x,  int y, int num, int dir) {
        map[x][y] = num;
        int mx = x+dx[dir];
        int my = y+dy[dir];

        if(canGo(mx, my) && num+1<=N*N &&!checked[num+1] ) {
            checked[num+1]= true;
            makeSnail(mx, my, num+1, dir);
            return;
        }
        //방향 전환
        int changeDir = (dir+1)%4;
        mx = x+dx[changeDir];
        my = y+dy[changeDir];
        if(canGo(mx, my) && num+1<=N*N &&!checked[num+1] ) {
            checked[num+1]= true;
            makeSnail(mx, my, num+1, changeDir);
        }
    }
    static boolean canGo(int x, int y) {
        return x>=0&& y>=0 && x<N && y<N&& map[x][y]==0;
    }
}