[BOJ] 1022번: 소용돌이 예쁘게 출력하기

https://www.acmicpc.net/problem/1022

1022번: 소용돌이 예쁘게 출력하기

 

 

알고리즘 분류

• 구현

 

문제 파악

0,0 지점으로부터 우, 상, 좌, 하로 돌아가면서 숫자가 증가하는 소용돌이에서

(r1, c1) ~ (r2, c2)의 범위까지의 숫자를 출력한다.

 

처음에는 BFS로 해결 해볼까 라는 생각에 이리저리 시도해봤지만 r2-r1+1 , c2-c1+1 만큼의 크기를 만들어서 계산을 해볼까 하다가 너무 복잡할 것 같아서 생각을 바꿨다.

 

(1,1), (2,2), (3,3) 순으로 이동해야 하는 거리가 늘어나며 정방향, 역방향을 설정해서 소용돌이처럼 x, y 좌표와 value를 설정해 나간다.

만약  x,y좌표가  r1, r2, c1, c2 범위 내에 있다면 ArrayList에 x, y, value 값을 add 해주고

Collections.sort를 통해 x, y로 정렬시킨 다음 출력해준다.

 

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

public class Main {
    static int r1,c1,r2,c2,cnt,len;
    static ArrayList<Point> list = new ArrayList<>();

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        r1 = Integer.parseInt(st.nextToken());
        c1 = Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());

        cnt = (Math.abs(r1-r2)+1) * (Math.abs(c1-c2)+1);

        int r = 0;
        int c = 0;

        int rt = 1;
        int ct = 1;

        int value = 1;
        int loop = 1;

        boolean reverseR = false;
        boolean reverseC = false;

        boolean init = true;

        while(init)
        {
            if(loop%2 == 0)
            {
                for(int idx = 0; idx<rt;idx++)
                {
                    init = AddElement(r,c,value);

                    if(!reverseR) r--;
                    else         r++;
                    value++;
                }
                rt++;
                reverseR = !reverseR;
            }
            else
            {
                for(int idx =0;idx<ct;idx++)
                {
                    init = AddElement(r,c,value);

                    if(!reverseC) c++;
                    else         c--;
                    value++;
                }
                ct++;
                reverseC = !reverseC;
            }
            loop++;
        }

        Collections.sort(list, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                if(o1.x == o2.x){
                    return o1.y - o2.y;
                }
                else{
                    return o1.x-o2.x;
                }
            }
        });

        String format = "%"+len+"d ";
        int enter = (c2-c1+1);
        for(int idx = 0; idx<list.size();idx++)
        {
            Point p = list.get(idx);
            int v = p.value;
            if(idx>0 && idx%enter == 0){
                System.out.println("");
            }
            System.out.printf(format,v);
        }
        br.close();
    }

    private static boolean AddElement(int r, int c,int value)
    {
        if(r1<=r && r<=r2 && c1<=c && c<=c2){
            list.add(new Point(r,c,value));
            len = Math.max(len,String.valueOf(value).length());
        }

        if(cnt == list.size()){
            return false;
        }
        return true;
    }
}

class Point
{
    int x;
    int y;
    int value;

    Point(int x, int y , int value){
        this.x = x;
        this.y = y;
        this.value = value;
    }
}