[백준][C#] 14503 로봇 청소기 - 골드5

문제 보기

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

14503번: 로봇 청소기

 

문제                           

 

 

입력                          

 

 

출력                          

 

 

풀이방법                 

지문을 그대로 구현하면 되는 문제이나

지문의 내용을 파악하는 게 힘들어 실수하기 쉽기 때문에

골드 5인 것으로 보인다.

 

나는 BFS적으로 접근해서 풀었으나, DFS든 무엇이든 상관은 없다.

서치보단 구현에 중점을 둔 문제이기 때문이다.

 

 

그리고 난 로봇 청소기의 입력이 (y, x, dr)로 들어오는데

당연히 (x, y, dr)의 순서일 것이라 생각하여 시간을 많이 뺏겼다.

혹시 잘 푼 것 같은데 이상하게 예제와 출력이 맞지 않는다면

의심 해보길 바란다...

 

 

 

로직을 어떻게 구현할까?

나는 이렇게 생각했다.

 

 

1. 시작 위치를 청소한다.

 

2. 현재 칸의 (바라보는 방향 기준) 서, 남, 동, 북 순으로 바로 옆 칸을 조사하여 청소가 되지 않았으면 그 칸으로 이동하고 고개를 돌린다.

 

3. 전부 청소가 되어있으면 뒷 칸이 벽인지 조사하고, 벽이 아니면 후진한다.

 

4. 주변 칸이 전부 청소되어있고 후진도 불가능할 때까지 반복한다.

 

 

이동한 칸, 방향을 계속 Queue에 집어넣고

Queue에 아무것도 없을 때까지 반복하였다.

그리고 청소할 때마다, count 변수에 1씩 더하였다.

 

코드로 확인해보자.

 

Queue<(int x, int y, int dr)> queue = new Queue<(int, int, int)>();

// 첫 칸을 큐에 넣음
queue.Enqueue((c, r, d));
// 첫 칸을 청소 (2로 바꿈)
maps[c, r] = 2;
int count = 1;

// 0북쪽 칸, 1동쪽 칸, 2남쪽 칸, 3서쪽 칸
int[] addX = { 0, 1, 0, -1 };
int[] addY = { -1, 0, 1, 0 };

while (queue.Count > 0)
{
	(int x, int y, int dr) = queue.Dequeue();

	// 방향 인덱스는 북동남서 시계인 반면, 탐색은 반시계로 진행하기 때문에 인덱스 감소
	for(int i = 3; i >= 0; i--)
	{
    	// 바라보는 방향 기준으로 탐색하기 위해, 현재 방향에 인덱스를 더하고 4로 나누어 주었다.
		int index = (i + dr) % 4;

		// 현재 방향에 있는 칸이 청소 안 됨
		if(maps[x + addX[index], y + addY[index]] == 0)
		{
        	// 큐에 넣어놓고 청소.
			queue.Enqueue((x + addX[index], y + addY[index], index));
			maps[x + addX[index], y + addY[index]] = 2;
			count++;
			
            // 어디든 청소하는 즉시 반복문에서 빠져나옴.
			break;
		}

		// 마지막 인덱스까지 갔을 경우
		if(i == 0)
        {
        	// 뒤가 벽이 아니라면
			if (maps[x + addX[(2 + dr) % 4], y + addY[(2 + dr) % 4]] != 1)
			{
            	// 큐에 넣는다. count는 변함 없음.
				queue.Enqueue((x + addX[(2 + dr) % 4], y + addY[(2 + dr) % 4], dr));
			}
		}
	}
}

 

구현하고 보면 그렇게 어려운 문제는 아니라 생각한다.

 

 

 

 

 

전체 코드

using System;
using System.Collections.Generic;

namespace BackjoonCodingTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string[] inputs = reader.ReadLine().Split();
            int N = int.Parse(inputs[0]);
            int M = int.Parse(inputs[1]);

            inputs = reader.ReadLine().Split();
            int r = int.Parse(inputs[0]);
            int c = int.Parse(inputs[1]);
            int d = int.Parse(inputs[2]);

            int[,] maps = new int[M, N];
            for(int i = 0; i < N; i++)
            {
                inputs = reader.ReadLine().Split();
                for(int j = 0; j < M; j++)
                {
                    maps[j, i] = int.Parse(inputs[j]);
                }
            }

            Queue<(int x, int y, int dr)> queue = new Queue<(int, int, int)>();

            queue.Enqueue((c, r, d));
            maps[c, r] = 2;
            int count = 1;

            int[] addX = { 0, 1, 0, -1 };
            int[] addY = { -1, 0, 1, 0 };

            while (queue.Count > 0)
            {
                (int x, int y, int dr) = queue.Dequeue();

                for(int i = 3; i >= 0; i--)
                {
                    int index = (i + dr) % 4;

                    if(maps[x + addX[index], y + addY[index]] == 0)
                    {
                        queue.Enqueue((x + addX[index], y + addY[index], index));
                        maps[x + addX[index], y + addY[index]] = 2;
                        count++;

                        break;
                    }

                    if(i == 0)
                    {
                        if (maps[x + addX[(2 + dr) % 4], y + addY[(2 + dr) % 4]] != 1)
                        {
                            queue.Enqueue((x + addX[(2 + dr) % 4], y + addY[(2 + dr) % 4], dr));
                        }
                    }
                }
            }

            print.WriteLine(count);

            reader.Close();
            print.Close();
        }
    }
}