[C#]프로그래머스/거리두기 확인/BFS

 

using System;
using System.Collections.Generic;
 
public class Solution
{
    //좌석의 최대 범위
    private const int placesLength = 5;
 
    public int[] solution(string[,] places)
    {
        List<int> answer = new List<int>(places.Length);
 
        for(int i = 0; i < places.GetLength(0); i++)
        {
            string[] room = new string[places.GetLength(1)];
 
            for (int j = 0; j < places.GetLength(1); j++)
            {
                room[j] = places[i, j];
            }
 
            answer.Add(CheckRoom(room));
        }
 
        return answer.ToArray();
    }
 
    private int CheckRoom(string[] room)
    {
        for(int i = 0; i < room.Length; i++)
        {
            for(int j = 0; j < room.Length; j++)
            {
                if (room[i][j] != 'P')
                    continue;
 
                //현재 좌석이 'P'인 경우, X를 벽, O를 경로, P를 목적지라고 생각하고 BFS를한다.
 
                Queue<(int, int)> queue = new Queue<(int, int)>();
                HashSet<(int, int)> checkAlready = new HashSet<(int, int)>();
 
                queue.Enqueue((i, j));
                checkAlready.Add((i, j));
 
                while(queue.Count > 0)
                {
                    (int y, int x) cur = queue.Dequeue();
 
                    var checkSeats = new List<(int, int)>();
 
                    //좌석을 검사하기 전에, 범위 안에 있는지부터 검사한다.
                    //상
                    if (cur.y > 0) 
                        checkSeats.Add((cur.y - 1, cur.x));
 
                    //하
                    if (cur.y < placesLength - 1) 
                        checkSeats.Add((cur.y + 1, cur.x));
 
                    //좌
                    if (cur.x > 0) 
                        checkSeats.Add((cur.y, cur.x - 1));
 
                    //우
                    if (cur.x < placesLength - 1) 
                        checkSeats.Add((cur.y, cur.x + 1));
 
                    foreach((int y, int x) seat in checkSeats)
                    {
                        //방문했으면 멈춤
                        if (checkAlready.Contains(seat))
                            continue;
 
                        char currentSeat = room[seat.y][seat.x];
 
                        //벽이 있으면 멈춤
                        if (currentSeat == 'X')
                            continue;
 
                        //P를 찾은 경우 = 거리두기를 안 지킨 것.
                        if (currentSeat == 'P')
                            return 0;
 
                        //맨헤튼거리가 2가 넘었다면 멈춤
                        if (CheckManhattan((seat.y, seat.x), (i, j)))
                            continue;
 
                        //공기가 통하는 길이 있으면 다시 체크한다.
                        if (currentSeat == 'O')
                        {
                            queue.Enqueue(seat);
                            checkAlready.Add(seat);
                        }
                    }
                }
            }
        }
 
        return 1;
    }
 
    private bool CheckManhattan((int, int) a, (int, int) b)
    {
        return (Math.Abs(a.Item1 - b.Item1) + Math.Abs(a.Item2 - b.Item2)) >= 2;
    }
}