[프로그래머스 C#] Lv.2 거리두기 확인하기

https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

각 대기실의 모든 좌표에 접근해서 사람이 있을 경우에 주변을 맨헤튼 거리만큼 탐색해 거리두기를 지키고 있는지 판단

- 단 한 사람이라도 거리두기를 지키지 않는다면 더 이상 탐색할 필요가 없으므로, 따로 처리 (isCheck)

 

BFS 탐색 ( 최단거리 )

결국 맨헤튼 거리는 대기실 내의 좌표를 기준으로 모든 방향에 대한 최단 거리가 됨

- 단, 모든 방향에 대한 이동을 할 때, 파티션이 있다면 이동하지 않아야 함

 -> 파티션이 양쪽으로 막혀있다면 도달하지 못함

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public int[] solution(string[,] places)
        {
            int[] answer = new int[places.GetLength(1)];

            // 대기실 개수 만큼 반복
            for (int i = 0; i < places.GetLength(0); i++)
            {
                bool isCheck = true; // 거리두기를 지키고 있는지 여부

                // 대기실 y, x 좌표는 무조건 5
                for (int y = 0; y < 5; y++)
                {
                    for (int x = 0; x < 5; x++)
                    {
                        // 대기실 내의 모든 좌표에 접근해 사람을 발견하면 BFS탐색
                        if (places[i, y][x] == 'P')
                            isCheck = BFS(i, y, x, places);

                        // 거리두기를 지키지 않는 대기실
                        if (isCheck == false)
                            break;
                    }

                    // 거리두기를 지키지 않는 대기실
                    if (isCheck == false)
                        break;
                }

                // 거리두기를 지키는 대기실일 경우 1로 바꿔줌
                if (isCheck)
                    answer[i] = 1;
            }

            return answer;
        }

        // 맨헤튼 거리만큼 주변을 탐색해 거리두기를 지키는지 여부를 반환
        public bool BFS(int i, int y, int x, string[,] places)
        {
            int[] dirY = new int[4] { 0, 0, 1, -1 };
            int[] dirX = new int[4] { 1, -1, 0, 0 };
            int maxDir = 2; // 탐색할 맨헤튼 거리

            var queue = new Queue<(int, int, int)>(); // posY, posX, dir
            queue.Enqueue((y, x, 0));

            // BFS 탐색
            while (queue.Count > 0)
            {
                var ints = queue.Dequeue();

                for (int j = 0; j < 4; j++)
                {
                    int posY = ints.Item1 + dirY[j];
                    int posX = ints.Item2 + dirX[j];
                    int dir = ints.Item3 + 1;

                    // 탐색 범위 벗어남
                    if (posY < 0 || posY > 4 || posX < 0 || posX > 4)
                        continue;

                    // 탐색중에 자기자신은 예외
                    if (posY == y && posX == x)
                        continue;

                    if (places[i, posY][posX] == 'P') // 거리두기를 지키지 않는 경우
                        return false;
                    else if (places[i, posY][posX] == 'O' && dir < maxDir) // 더 탐색
                        queue.Enqueue((posY, posX, dir));
                }
            }

            return true;
        }
    }