코딩테스트 준비 - 헌내기는 친구가 필요해

혼자서 다시푸는 코딩테스트 준비 일지 - 26

BFSDFS그래프 이론

Sep 26

7 min read

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 21736.헌내기는 친구가 필요해
사용언어 : C#
난이도 : 중하
풀이시간 : 미측정
유형 : DFS, BFS, 그래프 이론

문제

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.

도연이가 다니는 대학의 캠퍼스는 N×M $N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x $x$ , y $y$ )에 있다면 이동할 수 있는 곳은 (x+1 $x+1$ , y $y$ ), (x $x$ , y+1 $y+1$ ), (x−1 $x-1$ , y $y$ ), (x $x$ , y−1 $y-1$ )이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N $N$ (1≤N≤600$ 1 \leq N \leq 600 $), M$ M$ (1≤M≤600$ 1 \leq M \leq 600$)이 주어진다.

둘째 줄부터 N $N$ 개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

예제 입력 1 복사

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1 복사

예제 입력 2 복사

3 3
IOX
OXP
XPP

예제 출력 2 복사

TT

문제 풀이 접근

이 문제의 요구사항은 문제가 제시해준 칸을 구성하고, 제시해준 좌표에서 원하는 문자를 찾아서 카운팅을 할 수 있는가를 요구하는 문제였다.

크게 설명할 것은 없으니 플로우도 간단하다.
1. 주어진 값으로 맵을 만든다.
2. 주어진 좌표로 시작좌표를 설정한다.
3. DFS,BFS등 편한 방식으로 탐색하고 P를 발견했을 때, 변수를 하나 올려준다.

이 문제는 최단거리도 아니니, DFS로 풀어도 될것 같았지만, 난 BFS로 풀었다.

정답 작성 코드 (C#)

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;

/*
 * Difficulty : Easy ~ 
 * URL : https://www.acmicpc.net/problem/21736
 */


namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            //Case 0 _ Short
            Solution solution = new Solution();
            solution.solve();
        }
    }

    public class Solution
    {
        public int n;
        public int m;

        public char[,] maps;
        public bool[,] visited;

        public int[] dx = new int[4] { 0, 0, -1, 1 };
        public int[] dy = new int[4] { 1, -1, 0, 0 };

        public int startPosX;
        public int startPosY;

        int ret;
        public void solve()
        {
            ret = 0;

            string[] inputs = Console.ReadLine().Split(' ');

            n = Int32.Parse(inputs[1]);
            m = Int32.Parse(inputs[0]);
            // 좌우 바꾸기

            maps = new char[m, n];
            visited = new bool[m, n];

            for (int i =0; i < m;++i)
            {
                string inputLine = Console.ReadLine();

                for(int j = 0; j < inputLine.Length; ++j)
                {
                    char chr = inputLine[j];

                    maps[i, j] = chr;

                    if(chr == 'I')
                    {
                        startPosX = i;
                        startPosY = j;
                    }

                    if (chr == 'X')
                    {
                        visited[i, j] = true;
                    }
                }
            }

            BFS();

            Console.Write(ret == 0 ? "TT" : ret.ToString());
        }

        public void BFS()
        {
            var q = new Queue<Tuple<int, int>>();

            q.Enqueue(new Tuple<int, int>(startPosX, startPosY));

            while(q.Count > 0)
            {
                var dequeue = q.Dequeue();

                var posX = dequeue.Item1;
                var posY = dequeue.Item2;

                if (visited[posX, posY] == true)
                    continue;

                visited[posX, posY] = true;

                if (maps[posX, posY] == 'P')
                    ++ret;

                for(int i = 0; i < 4; ++i)
                {
                    int newPosX = posX + dx[i];
                    int newPosY = posY + dy[i];

                    if (isCheckSafeArea(newPosX, newPosY) == false)
                        continue;

                    if (visited[newPosX, newPosY] == true)
                        continue;

                    q.Enqueue(new Tuple<int,int>(newPosX ,newPosY));
                }
            }
        }

        public bool isCheckSafeArea(int posX, int posY)
        {
            if (posX < 0 || posX > (m - 1) || posY < 0 || posY > (n - 1))
                return false;

            return true;
        }
    }
}

코드 결과