[알고리즘] Part09 | 시뮬레이션

1.  시뮬레이션

1.1) 시뮬레이션

• 문제에 주어진 상황을 완벽하게 이해하고 이를 코드로 구현하는 과정
• 성능에 중점을 둔 다른 알고리즘과는 달리 구현에 중점

 

1.2) 시뮬레이션 문제 푸는 요령

• 문제를 읽고 pseudo code를 작성하기 (흐름대로)
• 조건 파악하기 (종료 조건, 상태가 변하는 조건)
• 문제에서 제공한 dir, r, c와 같은 값은 최대한 그대로 사용 (직관적인 이해 쉬워짐)
• 방향 회전의 경우 modulo 연산을 이용하면 쉽게 표현 가능 (연속적인 값 변화를 이용한 간단한 Trick)

 

2.  실습

2.1) 백준

• https://www.acmicpc.net/problem/17143
• https://www.acmicpc.net/problem/16236
• https://swexpertacademy.com/main/identity/user/requestUserPwModify.do
• https://www.acmicpc.net/problem/14503

 

2.2) G1_17143_낚시왕

package basic.Ch20_Simulation;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//사람 : 오른쪽으로 한 칸 씩 이동
//낚시 : 사람 열의 땅과 가장 가까운 상어 잡음
//상어 : 이동 / 벽이면 반대
//상어 겹치면 잡아먹음
//낚시왕이 잡은 상어 '크기 합' 출력
//이동 -> 낚시 -> 상어
public class G1_17143_낚시왕 {
    static int R, C, M, result;
    static int[][] arr;
    static Shark[][] shark;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, 1, -1};

    public static class Shark {
        int r, c, s, d, z;
        public Shark(int r, int c, int s, int d, int z) {
            this.r = r; //행
            this.c = c; //열
            this.s = s; //속력
            this.d = d; //이동 방향
            this.z = z; //크기
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        R = Integer.parseInt(st.nextToken()); //행
        C = Integer.parseInt(st.nextToken()); //열
        M = Integer.parseInt(st.nextToken()); //상어 수
        shark = new Shark[R][C];

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

            shark[r-1][c-1] = new Shark(r - 1, c - 1, s, d - 1, z);
        }

        simulation(0);
        System.out.print(result);
    }

    public static void simulation(int col){
        if(col == C) return;
        fishing(col);
        shark_move();
        simulation(col+1);
    }

    public static void fishing(int col){
        for (int i = 0; i < R; i++) {
            if(shark[i][col] != null){
                result += shark[i][col].z;
                shark[i][col] = null;
                return;
            }
        }
    }

    public static void shark_move(){
        Shark[][] moveshark = new Shark[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(shark[i][j] == null) continue;

                int ny = shark[i][j].r;
                int nx = shark[i][j].c;
                int s = shark[i][j].s;
                int d = shark[i][j].d;
                int z = shark[i][j].z;

                //gpt가 추가함
                if(d < 2) s %= (2*(R-1));
                else s %= (2*(C-1));

                for (int k = 0; k < s; k++) {
                    int ty = ny + dy[d];
                    int tx = nx + dx[d];

                    //벽 만나면 반대
                    if(ty < 0 || ty >= R || tx < 0 || tx >= C) {
                        d = (d % 2 == 0) ? d + 1 : d - 1;  // gpt가 만듦
                        ty = ny + dy[d];
                        tx = nx + dx[d];
                    }
                    ny = ty;
                    nx = tx;
                }
                if(moveshark[ny][nx] == null || z > moveshark[ny][nx].z) {
                    moveshark[ny][nx] = new Shark(ny, nx, s, d, z);
                }
            }
        }
        shark = moveshark;
    }
}

 

2.3) G3_16236_아기 상어

package basic.Ch20_Simulation;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
// 시물레이션
// 현재 아기상어 자리에서 반복적으로 최단경로의 물고기를 잡으러 가는 행위 반복 <= bfs
// 몇 초동안 계속 물고기를 먹을 수 있는 지 <= 계속 물고기를 먹는 동안 이동한 거리 <= bfs() 수행마다 걸린 시간(거리)
public class G3_16236_아기상어 {
    static int N, sy, sx, sSize, sEatCnt, ans;
    static int[][] map;

    // bfs
    static Queue<Node> queue = new ArrayDeque<>();
    static boolean[][] visit;
    // delta
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = {  0, 0,-1, 1 };

    public static void main(String[] args) throws Exception {
        // 입력, 자료구조
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int n = Integer.parseInt(st.nextToken());
                if( n == 9 ) { // 아기 상어
                    sy = i;
                    sx = j;
                }

                map[i][j] = n;
            }
        }

        // 시물레이션
        sSize = 2;

        // 반복횟수 미정 <= while
        while(true) {
            // 최단거리의 물고기를 먹었으면 먹는 과정에서 이동한 거리를 return, 못 먹으면 0 리턴
            int cnt = bfs();
            if( cnt == 0 ) break;
            ans += cnt;
        }

        System.out.println(ans);
    }
    // 최단거리의 물고기를 먹으려고 시도
    // 성공 : 이동한 거리(시간) 리턴
    // 실패 : 0 리턴
    static int bfs() {
        // 먹이 후보
        int minDis = Integer.MAX_VALUE; // bfs() 과정에서 먹을 수 있는 물고기를 찾으면 갱신
        int minY = Integer.MAX_VALUE;
        int minX = Integer.MAX_VALUE;

        // visit 초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visit[i][j] = false;
            }
        }

        // 현재 아기상어의 위치에서부터 시작
        visit[sy][sx] = true;
        queue.offer(new Node(sy, sx, 0));

        while( ! queue.isEmpty() ) {
            Node node = queue.poll();
            int y = node.y;
            int x = node.x;
            int d = node.d; // 상어위치부터 탐색해 온 거리

            // 먹을 수 있는 물고기를 만나면
            if( map[y][x] < sSize && map[y][x] != 0 ) {

                if( d < minDis ) { //  거리가 더 작은
                    minDis = d;
                    minY = y;
                    minX = x;
                }else if( d == minDis ) { // 거리가 같으면
                    if( y < minY ) {
                        minDis = d;
                        minY = y;
                        minX = x;
                    }else if( y == minY ) {
                        if( x < minX ) {
                            minDis = d;
                            minY = y;
                            minX = x;
                        }
                    }
                }
            } // if

            // 가지치기
            if( d + 1 >= minDis ) continue;

            // 4방탐색
            for (int i = 0; i < dx.length; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];

                // range, visit, size 체크
                if( ny < 0 || nx < 0 || ny >= N || nx >= N || visit[ny][nx] || map[ny][nx] > sSize ) continue;

                visit[ny][nx] = true;
                queue.offer(new Node(ny, nx, node.d + 1));
            } // for
        } // while

        // 물고기를 먹는 작업 성공/실패
        if( minDis == Integer.MAX_VALUE ) return 0; // 먹이를 찾지 못한 경우
        else { // 물고기를 찾아 먹은 경우 후처리
            sEatCnt++;
            if( sEatCnt == sSize ) {
                sSize++;
                sEatCnt = 0;
            }
            map[minY][minX] = 0; // 먹은 물고기 자리
            map[sy][sx] = 0; // 상어가 출발한 자리

            sy = minY;
            sx = minX;
        }

        return minDis;
    }

    static class Node{
        int y, x, d; // d: 거리
        Node(int y, int x, int d){
            this.y = y; this.x = x; this.d = d;
        }
    }
}

 

2.4) G5_14503_로봇 청소기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//로봇청소기와 방 주어졌을 때, 청소 영역의 개수
//방 NxM (r,c)
//로봇청소기 (동서남북)
//현재 칸 청소
//동서남북 청소 됨 -> 후진 (뒤에 벽있으면 작동 중지)
//안됨 -> 반시계 90도 회전 후 청소

public class Main {
    static int N, M, result;
    static Robot robot;
    static int[][] arr;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static class Robot {
        int r, c, d;
        Robot(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        robot = new Robot(r, c, d);

        arr = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        result = 0;
        cleanRoom();
        System.out.println(result);
    }

    public static void cleanRoom() {
        while (true) {
            if (arr[robot.r][robot.c] == 0) {
                arr[robot.r][robot.c] = 2;
                result++;
            }

            boolean cleaned = false;
            for (int i = 0; i < 4; i++) {
                robot.d = (robot.d + 3) % 4;
                int ny = robot.r + dy[robot.d];
                int nx = robot.c + dx[robot.d];

                if (ny >= 0 && ny < N && nx >= 0 && nx < M && arr[ny][nx] == 0) {
                    robot.r = ny;
                    robot.c = nx;
                    cleaned = true;
                    break;
                }
            }

            if (!cleaned) {
                int backY = robot.r - dy[robot.d];
                int backX = robot.c - dx[robot.d];

                if (backY >= 0 && backY < N && backX >= 0 && backX < M && arr[backY][backX] != 1) {
                    robot.r = backY;
                    robot.c = backX;
                } else {
                    break;
                }
            }
        }
    }
}