백준 1952 : 달팽이2

문제 링크

오늘의 재활훈련은 사방탐색으로 한다.
DFS 문제를 떠올리면서 전역 변수로 di, dj를 만들고 방문처리 배열을 만들면 되겠다 라는 생각.
하지만 여기서 생각한건 방문처리 배열까지는 만들겠으나, 좌표 저장할 배열을 굳이 만들 필요가 있을까? DFS를 쓸 것도 아니라 다시 돌아올 필요가 없는데?
따라서 2차원 int 배열 만들 필요 없이 boolean만 만들자고 생각했다.

그렇다면 차례차례 코딩해보면 될 것 같다.

    static int[] di = {0, 1, 0, -1}; // 행 : 우 하 좌 상
    static int[] dj = {1, 0, -1, 0}; // 열
//    static int[][] map;
    static int N, M;
    static boolean[][] visited;

map 배열은 필요없다고 이미 머릿속에서 인지했다. 우리는 달팽이가 턴한 횟수를 카운팅하고 종료조건으로 sum 카운팅을 하자.

public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
//        map = new int[M][N];
        visited = new boolean[M][N];
        int i = 0, j = 0;
        int dir = 0; // 0, 1, 2, 3 우 하 좌 상
        int cnt = 0;
        int sum = 1;
        visited[0][0] = true;

dir은 방향을 나타내기 위한 변수
cnt는 달팽이가 회전한 횟수
sum은 배열을 밟은 횟수
첫번째 (0,0)은 바로 밟았기 때문에 방문했다는 처리를 해둔다.

while (true) {
            if(sum==M*N) break;

            int ni = i + di[dir];
            int nj = j + dj[dir];

            // 경계조건
            if (ni >= 0 && ni < M && nj >= 0 && nj < N && !visited[ni][nj]) {
                // 충족 시 해당 방향으로 전진
                visited[ni][nj] = true;
                i = ni;
                j = nj;
                sum++;
            } else { // 미충족 시 방향 전환과 카운팅
                dir = (dir + 1) % 4;
                cnt++;
            }
        }
        System.out.println(cnt);
    }

종료조건으로는 sum이 M과 N의 곱이 되면 된다.
경계조건은 방문처리 문제에서 끊임없이 나오는 것이기 때문에 한 번 정리해두는 것이 좋다.
행과 열이 0 앞으로 갈 수 없고 M, N 뒤로 갈 수 없다. 그렇기 때문에 해당 M과 N 내에 반드시 존재해야 하며, 달팽이가 앞으로 전진하기 위해서는 방문 배열이 false, 즉 밟아본 적이 없어야 한다.
이 조건을 충족했을 시에 해당 배열을 true로 만들어주는 동시에, (i,j)를 업데이트 해준다. 그리고 sum을 카운팅함으로써 밟은 횟수를 업데이트 한다.
만일 저 경계조건을 충족하지 못했다는 의미는, 앞으로 전진할 수 없음을 의미, 즉 달팽이가 해당 루트로는 다 돌았으니 턴을 할 차례라는 것이다. 회전을 해야하기 때문에 dir에 1을 더해준다.

하지만 dir+1로 업데이트 해주면 문제가 생기는데,
%4 처리를 해주지 않는다면 3(상) 이후에 사방탐색을 반복하지 못하기 때문에 반드시 % 처리를 해준다.

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

public class Main {

    static int[] di = {0, 1, 0, -1}; // 행 : 우 하 좌 상
    static int[] dj = {1, 0, -1, 0}; // 열
//    static int[][] map;
    static int N, M;
    static boolean[][] visited;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
//        map = new int[M][N];
        visited = new boolean[M][N];
        int i = 0, j = 0;
        int dir = 0; // 0, 1, 2, 3 우 하 좌 상
        int cnt = 0;
        int sum = 1;
        visited[0][0] = true;
        while (true) {
            if(sum==M*N) break;

            int ni = i + di[dir];
            int nj = j + dj[dir];

            // 경계조건
            if (ni >= 0 && ni < M && nj >= 0 && nj < N && !visited[ni][nj]) {
                // 충족 시 해당 방향으로 전진
                visited[ni][nj] = true;
                i = ni;
                j = nj;
                sum++;
            } else { // 미충족 시 방향 전환과 카운팅
                dir = (dir + 1) % 4;
                cnt++;
            }
        }
        System.out.println(cnt);


    }
}

완성 코드는 위와 같다.