*완전 탐색* seat

완전 탐색 관련 문제입니다.

핵심

문제에서 좌표로 주어진 자리를 우리는 배열을 이용해서 표현해야 한다. 즉 좌표를 x축으로 대칭시킨 모습이 배열과 같다.

 

정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int width = sc.nextInt(); // 공연장의  가로길이
        int height = sc.nextInt();  // 공연장의 세로길이
        int order = sc.nextInt(); // 대기순서
        int x = 0, y = -1;
        boolean down = true, up = false, right = false, left = false; // 시계방향으로 탐색할 수 있도록 도와주는 변수

        int[][] arr = new int[height][width]; // 공연장의 좌석배열
        
        if (order > width * height) { // 공연장의 좌석보다 대기순서가 크게 되면 0을 출력하고 return
            System.out.println(0);
            return;
        }

        for (int i = 1; i <= order; i++) { // 대기순서 만큼 반복

            if (down && y + 1 < height && arr[y + 1][x] == 0) { // 아래쪽으로 탐색
                arr[y + 1][x] = i ;
                y++;
                continue;
            } else { // 아래쪽이 다 탐색이 끝나면 오른쪽으로 이동해야 하기 때문에 right를 제외하고 모두 false
                down = false;
                up = false;
                right = true;
                left = false;
            }

            if (right && x + 1 < width && arr[y][x + 1] == 0) { // 오른쪽으로 탐색
                arr[y][x + 1] = i ;
                x++;
                continue;
            } else { // 오른쪽 탐색이 모두 끝나면 위쪽으로 이동해야 하기 떄문에 up을 제외하고 모두 false
                down = false;
                up = true;
                right = false;
                left = false;
            }
            if (up && y - 1 >= 0 && arr[y - 1][x] == 0) { // 위쪽으로 탐색
                arr[y - 1][x] = i ;
                y--;
                continue;
            } else { // 위쪽 탐색이 모두 끝나면 왼쪽으로 이동해야 하기 때문에 left를 제외하고 모두 false
                down = false;
                up = false;
                right = false;
                left = true;
            }
            if (left && x - 1 >= 0 && arr[y][x - 1] == 0) { // 왼쪽으로 탐색
                arr[y][x - 1] = i ;
                x--;
                continue;
            } else { // 왼쪽 탐색이 모두 끝나면 아래쪽으로 이동해야 하기 때문에 down을 제외하고 모두 false
                i--; // 아래쪽으로 탐색하는 로직(첫번쨰 if문)이 제일 위쪽에 있어서 i변수를 --해주어여함.
                down = true;
                up = false;
                right = false;
                left = false;
            }

        }

        System.out.println((x + 1) + " " + (y + 1));
    }
}

 

해설

가로, 세로, 인원을 받는다. 만약 인원의 수가 가로*세로의 값보다 커질 경우에 0을 출력하고 종료한다.

좌표를 x축으로 대칭시킨 배열 안에 값을 넣어준다.

즉 아래 -> 오른쪽 -> 위 -> 왼쪽 순으로 반복된다.

boolean 타입으로 각 방향을 지정해준다.

각 방향마다 가로와 세로의 길이의 길이까지 대입되고, 전부 대입하면 다음 방향으로 전환한다.

자세한 설명은 주석처리로 되어있어 이해가 안 된다면, 주석을 자세히 보면 도움이 된다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.