[BOJ] 5913. Grazing Patterns (bruteforce)

#. Problem

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

* The copyright in this matter is in acmicpc

#. Resolution Process

1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it

#. Solve

정보
- 5x5 크기의 땅
- Bessie와 Mildred는 각각 (1,1) (5,5)에서 풀을 먹기 시작
- 식사는 30분 소요
- 식사  후 인접한 잔디칸으로 이동 (30분 소요) -> 항상 잔디가 있는 칸으로만 이동
- 마지막에는 같은 칸에서 만나기 -> 마지막을 제외하고 같은 칸에서 만날 수 없음
- 위를 만족하는 경우의 수를 구하자.


처음에는 Bessie와 Mildred가 동시에 이동 가능한 모든 경로로 다 탐색해보는 뤼얼 브루트포스 방법으로 접근했었다.
하지만..! 조금만 다른 시각으로 문제를 바라보면 더 효율적인 방법이 있었는데..

그것은.. Bessie는  Mildred가 있는 공간으로 이동할 수 있는지를 확인하는 방법이다.

(1,1)에서 (5,5)로 도달할 수 있는 경로의 수.

첫 번째 방법은 Bessie와 Mildred 모두를 신경써주어야 했지만,
두 번째 방법은 한 마리의 소만 신경써주면 된다.

 

멈추면 비로소 보이는.. ..

 

아직도 수련이 많이 필요하다. :(

#. Code Ver1.

import java.io.*;
import java.util.*;
 
public class Main {
 
    FastScanner in;
    PrintWriter out;
 
    static class Point {
        int x, y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int cntCase = 0, cntGrass;
    static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    static boolean[][] isRock;
    void solve() {
        int K = in.nextInt();
        isRock = new boolean[5][5];
        cntGrass = 25 - K;
        // 사각형을 시계 반대 방향으로 90도 돌려서 생각
        for (int i = 0; i < K; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            isRock[x - 1][y - 1] = true; // 돌의 위치 
        }
        
        // 시작 위치
        isRock[0][0] = true;
        isRock[4][4] = true;
        cntGrass-=2;
        start(0, 0, 4, 4);
        
        out.println(cntCase);
    }
    
    private void start(int bx, int by, int mx, int my) {
        
        // 잔디가 모두 없어졌을 경우
        if (cntGrass == -1) {
            // B와 M이 같은 공간에 위치
            if (bx == mx && by == my) {
                cntCase++;
            } else {
                return;
            }
        }
        
        // B와 M이 만났는데 잔디가 남았을 경우
        if (bx == mx && by == my && cntGrass > -1) return;
 
        // B와 M가 이동
        for (int d1 = 0; d1 < 4; d1++) {
            // B가 이동할 곳에 바위가 있거나 필드를 벗어나면 pass 
            if (!canMove(bx, by, d1)) continue;
            
            for (int d2 = 0; d2 < 4; d2++) {
                // M가 이동할 곳에 바위가 있거나 필드를 벗어나면 pass
                if (!canMove(mx, my, d2)) continue;
                
                Point nextBs = new Point(bx + dx[d1], by + dy[d1]);
                Point nextMd = new Point(mx + dx[d2], my + dy[d2]);
                
                // 해당 위치로 이동해서 잔디 식사
                cntGrass-=2;
                isRock[nextBs.x][nextBs.y] = true;
                isRock[nextMd.x][nextMd.y] = true;
                
                // 재귀
                start(nextBs.x, nextBs.y, nextMd.x, nextMd.y);
                
                // 돌아오면 잔디 다시 뱉기
                cntGrass+=2;
                isRock[nextBs.x][nextBs.y] = false;
                isRock[nextMd.x][nextMd.y] = false;
            }
        }
    }
 
    private Boolean canMove(int x, int y, int d) {
        
        int xx = x + dx[d];
        int yy = y + dy[d];
        // 필드를 벗어날 경우
        if (xx  > 4 || yy  > 4 || xx < 0 || yy < 0) return false;
        // 바위가 있는 경우
        if (isRock[xx][yy]) return false;
        
        return true;
    }
 
    /********************************** Input function **********************************/
    
    void run() {
        in = new FastScanner();
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
 
    public static void main(String[] args) {
        new Main().run();
    }
 
    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
 
        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(nextToken());
        }
 
        long nextLong() {
            return Long.parseLong(nextToken());
        }
 
        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}

#. Code Ver2.

import java.io.*;
import java.util.*;
 
public class Main {
 
    FastScanner in;
    PrintWriter out;
 
    static int cntCase = 0, cntGrass;
    static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    static boolean[][] isRock;
    void solve() {
        int K = in.nextInt();
        isRock = new boolean[5][5];
        cntGrass = 25 - K;
        // 사각형을 시계 반대 방향으로 90도 돌려서 생각
        for (int i = 0; i < K; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            isRock[x - 1][y - 1] = true; // 돌의 위치 
        }
        
        // 시작 위치
        isRock[0][0] = true;
        cntGrass--;
        start(0, 0);
        
        out.println(cntCase);
    }
    
    private void start(int x, int y) {
        
        // Mildred의 위치에 도달 
        if (x == 4 && y == 4) {
            // 모든 잔디를 섭취
            if (cntGrass == 0) cntCase++;
            else return;
        }
        
        // Mildred의 위치에 도달하지 않았는데 남은 잔디가 없을 경우
        if (cntGrass == 0 && !(x == 4 && y == 4)) return;
 
        // Bessie가 이동
        for (int d = 0; d < 4; d++) {
            //Bessie가 이동할 곳에 바위가 있거나 필드를 벗어나면 pass 
            if (!canMove(x, y, d)) continue;
            
            int xx = x + dx[d];
            int yy = y + dy[d];
            
            // 해당 위치로 이동해서 잔디 식사
            cntGrass--;
            isRock[xx][yy] = true;
            
            // 재귀
            start(xx, yy);
            
            // 돌아오면 잔디 다시 뱉기
            cntGrass++;
            isRock[xx][yy] = false;
        }
    }
 
    private Boolean canMove(int x, int y, int d) {
        
        int xx = x + dx[d];
        int yy = y + dy[d];
        // 필드를 벗어날 경우
        if (xx  > 4 || yy  > 4 || xx < 0 || yy < 0) return false;
        // 바위가 있는 경우
        if (isRock[xx][yy]) return false;
        
        return true;
    }
 
    /********************************** Input function **********************************/
    
    void run() {
        in = new FastScanner();
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
 
    public static void main(String[] args) {
        new Main().run();
    }
 
    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
 
        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(nextToken());
        }
 
        long nextLong() {
            return Long.parseLong(nextToken());
        }
 
        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}