백준 17406 (배열 돌리기 4) - java

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

17406번: 배열 돌리기 4

백트랙킹과 구현을 응용한 문제였다.

• 문제의 조건에 맞게 배열을 돌릴 수 있는가 !
• 백트랙킹을 논리에 맞게 적용할 수 있는가 !

배열 돌리는 방법

그림의 예시로 설명하겠다. 배열을 돌리는 방법은 첫번째 행, 마지막 행, 첫번째 열, 마지막 열에 대해 반복문을 수행하는 것이다.(사이클이라 명하겠다)

이 때 생각해야 할 점은 위의 작업은 반복된다는 것이다. 반복의 조건을 위해서는 sx, sy, lx, ly를 알아야 한다. 문제의 조건에서 주어지는데한번의 사이클이 수행되고 나서 (sx , sy ,lx ,ly ) -> (sx +1, sy +1, lx -1, ly-1) 로 변경한다. 그리고 sx나 sy중 하나라도 lx,ly와 값이 같거나 역전되었다면 반복문이 종료된다.

 

move 메소드

    static void move(int sx,int sy,int lx,int ly)
    {
        copy();

        while(true)
        {
            for(int i=ly;i>sy;i--)
            {
                board[sx][i] = tmp[sx][i-1];
            }

            for(int i=sx;i<lx;i++)
            {
                board[i][sy] = tmp[i+1][sy];
            }

            for(int i=sy;i<ly;i++)
            {
                board[lx][i] = tmp[lx][i+1];
            }

            for(int i=lx;i>sx;i--)
            {
                board[i][ly] = tmp[i-1][ly];
            }

            sx = sx +1;
            sy = sy + 1;
            lx = lx -1;
            ly = ly -1;

            if(lx<=sx||ly<=sy)
                break;
        }
    }

백트랙킹

• 종료 조건은 주어진 k개의 연산을 모두 수행했는가이다.
• 각 연산에 대해 번호를 부여하고 방문 배열을 통해 정석적인 백트랙킹을 실행하면 된다.

 

전체 코드

import java.io.*;
import java.util.*;
public class Main {
    static int n = 0;
    static int m = 0;
    static int k = 0;
    static int[][] board = new int[51][51];
    static int[][] tmp = new int[51][51];
    static boolean[] visit = new boolean[18];
    static turn[] arr = new turn[18];
    static int result = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=m;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1;i<=k;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            turn t = new turn(r,c,s);
            arr[i] = t;

        }
        travel(1);
        System.out.println(result);
        br.close();

    }
    static void travel(int cur)
    {
        // k개의 연산을 모두 수행했을 때
        if(cur>k)
        {
            int first = Integer.MAX_VALUE;
            for(int i=1;i<=n;i++)
            {
                int tmp =0;
                for(int j=1;j<=m;j++)
                    tmp +=board[i][j];

                first = Math.min(first,tmp); // 각 행의 더한 값의 최솟값 구하기
            }

            result = Math.min(result,first); // 해당 최솟값과 결과값 비교 (최솟값 찾기)
            return;
        }
        for(int i=1;i<=k;i++)
        {
            if(!visit[i])
            {
                visit[i] = true;
                move(arr[i].r-arr[i].s,arr[i].c-arr[i].s,arr[i].r+arr[i].s,arr[i].c+arr[i].s);
                travel(cur + 1);
                re_move(arr[i].r-arr[i].s,arr[i].c-arr[i].s,arr[i].r+arr[i].s,arr[i].c+arr[i].s);
                visit[i] = false;
            }
        }
    }
    
    // 배열 복사
    static void copy()
    {
        tmp = new int[51][51];

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                tmp[i][j] = board[i][j];
        }
    }
    // 배열 한칸 씩 이동
    static void move(int sx,int sy,int lx,int ly)
    {
        copy();

        while(true)
        {
            for(int i=ly;i>sy;i--)
            {
                board[sx][i] = tmp[sx][i-1];
            }

            for(int i=sx;i<lx;i++)
            {
                board[i][sy] = tmp[i+1][sy];
            }

            for(int i=sy;i<ly;i++)
            {
                board[lx][i] = tmp[lx][i+1];
            }

            for(int i=lx;i>sx;i--)
            {
                board[i][ly] = tmp[i-1][ly];
            }

            sx = sx +1;
            sy = sy + 1;
            lx = lx -1;
            ly = ly -1;

            if(lx<=sx||ly<=sy)
                break;
        }
    }
    // 반대로 되돌리기 ( 배열 상태 복원을 위해 사용)
    static void re_move(int sx,int sy,int lx,int ly)
    {
        copy();

        while(true)
        {
            for(int i=sy;i<ly;i++)
            {
                board[sx][i] = tmp[sx][i+1];
            }

            for(int i=lx;i>sx;i--)
            {
                board[i][sy] = tmp[i-1][sy];
            }

            for(int i=ly;i>sy;i--)
            {
                board[lx][i] = tmp[lx][i-1];
            }

            for(int i=sx;i<lx;i++)
            {
                board[i][ly] = tmp[i+1][ly];
            }

            sx = sx +1;
            sy = sy + 1;
            lx = lx -1;
            ly = ly -1;

            if(lx<=sx||ly<=sy)
                break;
        }
    }
}
class turn
{
    int r;
    int c;
    int s;

    turn(int r,int c,int s)
    {
        this.r = r;
        this.c = c;
        this.s = s;
    }
}