코딩테스트 준비 - 그림

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

• 응시 사이트 : BOJ

• 문제 : 1926.그림

• 사용언어 : C#

• 난이도 : 중

• 풀이시간 : 01h 10m

• 유형 : BFS, DFS, 그래프 이론

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제 입력 1 복사

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1 복사

4
9

문제 풀이 접근

이 문제는, BFS 중 새로운 문제를 풀려고 했는데, 이전에 못푼 문제가 있어서 읽어보니 못풀이유가 없는데하면서 그냥 풀어봤다.

크게 어려운건 없고, maps, visited 구성해서 순회돌리면 자동으로 풀리고 오름차순으로 정렬해서 0번째 출력하면된다.

말한것과는 다르게 시간은 조금 걸린편인데, 괜히 입력 문자열 공백없애는 다른 방법 구상해본다고 split 쓰다가 replace 써서 2자리 이상 숫자를 입력받았을때 오류나는것을 캐치못해서 시간이 오래걸렸다.

정답 작성 코드 (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.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography;
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 : Middle
 * URL : https://www.acmicpc.net/problem/1926
 * Time : 01h 10m , Failed
 */


namespace CodingTestProj
{
    internal class Program
    {


        static void Main(string[] args)
        {
            //Case 0 _ Short
            Solution solution = new Solution();
            solution.solve();
        }
    }
    public class Solution
    {
        int n;
        int m;

        int[,] maps;
        bool[,] visited;

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

        List<int> retList = new List<int>();

        public void solve()
        {
            string[] input = Console.ReadLine().Split(' ');

            n = Convert.ToInt32(input[0].ToString());
            m = Convert.ToInt32(input[1].ToString());

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

            for (int i = 0; i < maps.GetLength(0); i++)
            {
                input = Console.ReadLine().Split(' ');

                for (int j = 0; j < input.Length; ++j)
                {
                    maps[i, j] = Convert.ToInt32(input[j].ToString());

                    if (maps[i, j] == 0)
                        visited[i, j] = true;
                }
            }

            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < m; ++j)
                {
                    if (visited[i, j] == false)
                    {
                        int posX = i;
                        int posY = j;
                        BFS(posX, posY);
                    }
                }
            }
            Print();
        }
        public void BFS(int posX, int posY)
        {
            Queue<Tuple<int, int>> q = new Queue<Tuple<int, int>>();

            q.Enqueue(new Tuple<int, int>(posX, posY));
            int ret = 0;
            ++ret;

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

                int curPosX = deq.Item1;
                int curPosY = deq.Item2;

                visited[curPosX, curPosY] = true;

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

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

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

                    visited[newPosX, newPosY] = true;

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

            retList.Add(ret);
        }

        public bool CheckSafeArea(int newPosX, int newPosY)
        {
            if (newPosX < 0 || newPosY < 0 || newPosX > (n - 1) || newPosY > (m - 1))
                return false;

            return true;
        }

        public void Print()
        {
            retList.Sort((int a, int b) => { return b.CompareTo(a); });
            Console.WriteLine(retList.Count);
            int ret = retList.Count == 0 ? 0 : retList[0];
            Console.WriteLine(ret);
        }
    }
}

코드 결과