[ BOJ/C# ] 14503 로봇 청소기

BFS 문제

 

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

14503번: 로봇 청소기

BFS에서 자주 사용되는 Queue를 사용할까 했지만 이차원배열로 푸는 방법이 머리속으로 딱 그려져 풀어보았다. 

BFS는 글로 먼저 적으며 나 자신도 이해하고 푸는 것이 중요하다고 생각한다. 

 

using System;
using System.IO;

namespace _14503
{
    class Program
    {
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());

            int[,] room = null;
            int[] robot = new int[2];
            int d = 0;
            int cleanRoom = 0;

            int index = 0;
            while (true)
            {
                //입력 조건
                if (index == 0)
                {
                    //방의 크기
                    string[] roomStr = sr.ReadLine().Split(' ');
                    int n = int.Parse(roomStr[0]);
                    int m = int.Parse(roomStr[1]);
                    room = new int[n, m];

                    index++;
                }
                else if(index == 1)
                {
                    //로봇의 초기 좌표, 방향 d
                    string[] robotStrs = sr.ReadLine().Split(' ');
                    robot[0] = int.Parse(robotStrs[0]);
                    robot[1] = int.Parse(robotStrs[1]);
                    d = int.Parse(robotStrs[2]);

                    index++;
                }
                else
                {
                    //각 방의 상태
                    if (index - 1 > room.GetLength(0)) break;

                    string[] roomStr = sr.ReadLine().Split(' ');

                    for (int i = 0; i < room.GetLength(1); i++)
                    {
                        room[index-2, i] = int.Parse(roomStr[i]);
                        //Console.WriteLine("{0}, index{1}", room[index - 2, i], index);
                    }

                    //Console.WriteLine("{0}, {1}", index-1, room.GetLength(0));
                    index++;
                }
            }

            //청소 시작
            int r = robot[0];
            int c = robot[1];
            //Console.WriteLine("{0}, {1}", robot[0], robot[1]);

            while (true)
            {

                //1. 현재 칸이 아직 청소되지 않은 경우(0일 경우), 현재 칸을 청소한다.
                //임의로 벽이 없는 청소된 방을 -1로 지정함
                if (room[r, c] == 0) 
                { 
                    room[r, c] = -1;
                    cleanRoom++;
                };

                //2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
                if (room[r + 1, c] != 0&& room[r - 1, c] != 0&& room[r, c+1] != 0 && room[r, c-1] != 0)
                {
                    //1) 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
                    //2) 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
                    if (d == 0 && room[r + 1, c] == -1) r = r + 1;
                    else if (d == 1 && room[r, c - 1] == -1) c = c - 1;
                    else if (d == 2 && room[r - 1, c] == -1) r = r - 1;
                    else if (d == 3 && room[r, c + 1] == -1) c = c + 1;
                    else break;
                }
                else  //3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
                {
                    //1) 반시계 방향으로 90도 회전한다.
                    if (d == 0) d = 3;
                    else d--;

                    //2) 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
                    if (d == 0 && room[r - 1, c] == 0) r = r - 1;
                    else if (d == 1 && room[r, c + 1] == 0) c = c + 1;
                    else if (d == 2 && room[r + 1, c] == 0) r = r + 1;
                    else if (d == 3 && room[r, c - 1] == 0) c = c - 1;
                }
            }
            Console.WriteLine(cleanRoom);
            sr.Close();
        }
    }
}