Print Friendly and PDF

기타/코딩테스트 공부

[필수 알고리즘] 시뮬레이션

나는야 개발자 2025. 5. 3. 17:51
반응형

시뮬레이션이란?

- 각 조건에 맞는 상황을 구현하는 문제(지도상에서 이동하면서 탐험?하는 문제, 배열 안에서 이동하면서 탐험? 하는 문제)

- 별도 알고리즘 없이 풀수 있으나, 구현력이 중요

- 매 시험마다 1문제 이상 무조건 출제

 

시간복잡도

- N * M

- 각 칸에서 4방향 연산 수행

 

자료구조

- 전체 지도 int[][]

- 내 위치, 방향; int, int, int

 

문제풀이

- 백준 14503

 

1.

 // 입력 받기
string[] input = Console.ReadLine().Split();
int N = int.Parse(input[0]);
int M = int.Parse(input[1]);

input = Console.ReadLine().Split();
int y = int.Parse(input[0]);
int x = int.Parse(input[1]);
int d = int.Parse(input[2]);

int[][] map = new int[N][];
for (int i = 0; i < N; i++)
{
    input = Console.ReadLine().Split();
    map[i] = new int[M];
    for (int j = 0; j < M; j++)
    {
        map[i][j] = int.Parse(input[j]);
    }
}

int cnt = 0;
int[] dy = { -1, 0, 1, 0 };  // 북, 동, 남, 서
int[] dx = { 0, 1, 0, -1 };

- 입력값 에 대한 선언과 북동남서 값 선언

 

2.

 while (true)
        {
            // 현재 칸이 청소되지 않은 경우 청소
            if (map[y][x] == 0)
            {
                map[y][x] = 2;  // 청소 완료 표시
                cnt++;
            }
}

- while문을 선언하고 청소되지 않은 칸이면 청소 처리

 

3.

bool sw = false;

// 4방향 탐색
for (int i = 1; i <= 4; i++)
{
    // 반시계 방향으로 회전 (d-i+4)%4
    int nd = (d - i + 4) % 4;
    int ny = y + dy[nd];
    int nx = x + dx[nd];

    if (0 <= ny && ny < N && 0 <= nx && nx < M)
    {
        if (map[ny][nx] == 0)
        {
            d = nd;
            y = ny;
            x = nx;
            sw = true;
            break;
        }
    }
}

- 4방향으로 탐색을 할때 반시계 방향으로 하라고 했으니 "(d - i + 4) % 4;"로 해서 반 시계 방향으로 돌며 빈 공간 찾기

 

4.

// 4방향 모두 갈 수 없는 경우
if (!sw)
{
    // 후진 방향 계산
    int ny = y - dy[d];
    int nx = x - dx[d];

    if (0 <= ny && ny < N && 0 <= nx && nx < M)
    {
        if (map[ny][nx] == 1)  // 벽이면 종료
        {
            break;
        }
        else  // 벽이 아니면 후진
        {
            y = ny;
            x = nx;
        }
    }
    else  // 범위를 벗어나면 종료
    {
        break;
    }
}

- 만약 4방향 모두 청소할 곳이 없다면 현재 방향을 유지한 상태에서 반대 방향으로 이동

- 범위를 벗어나거나 벽이면 종료

 

최종코드

public class num_14503
{
    static void Main(string[] args)
    {
        // 입력 받기
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        input = Console.ReadLine().Split();
        int y = int.Parse(input[0]);
        int x = int.Parse(input[1]);
        int d = int.Parse(input[2]);

        int[][] map = new int[N][];
        for (int i = 0; i < N; i++)
        {
            input = Console.ReadLine().Split();
            map[i] = new int[M];
            for (int j = 0; j < M; j++)
            {
                map[i][j] = int.Parse(input[j]);
            }
        }

        int cnt = 0;
        int[] dy = { -1, 0, 1, 0 };  // 북, 동, 남, 서
        int[] dx = { 0, 1, 0, -1 };

        while (true)
        {
            // 현재 칸이 청소되지 않은 경우 청소
            if (map[y][x] == 0)
            {
                map[y][x] = 2;  // 청소 완료 표시
                cnt++;
            }

            bool sw = false;

            // 4방향 탐색
            for (int i = 1; i <= 4; i++)
            {
                // 반시계 방향으로 회전 (d-i+4)%4
                int nd = (d - i + 4) % 4;
                int ny = y + dy[nd];
                int nx = x + dx[nd];

                if (0 <= ny && ny < N && 0 <= nx && nx < M)
                {
                    if (map[ny][nx] == 0)
                    {
                        d = nd;
                        y = ny;
                        x = nx;
                        sw = true;
                        break;
                    }
                }
            }

            // 4방향 모두 갈 수 없는 경우
            if (!sw)
            {
                // 후진 방향 계산
                int ny = y - dy[d];
                int nx = x - dx[d];

                if (0 <= ny && ny < N && 0 <= nx && nx < M)
                {
                    if (map[ny][nx] == 1)  // 벽이면 종료
                    {
                        break;
                    }
                    else  // 벽이 아니면 후진
                    {
                        y = ny;
                        x = nx;
                    }
                }
                else  // 범위를 벗어나면 종료
                {
                    break;
                }
            }
        }

        Console.WriteLine(cnt);
    }
}

 

참고영상

- 바로가기

 

 

 

반응형

'기타 > 코딩테스트 공부' 카테고리의 다른 글

[필수 알고리즘] 이진탐색  (0) 2025.05.03
[필수 알고리즘] 투포인터  (0) 2025.05.03
[필수 알고리즘] 백 트래킹  (0) 2025.05.03
[필수 알고리즘] DFS  (0) 2025.05.03
[필수 알고리즘] BFS  (0) 2025.05.03