[코딩테스트] BOJ 1926 그림 (성공)

 

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

 

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 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

 

 

풀이

입력으로 그림이 주어지고, 그림이 몇개인지와 가장 넓은 그림의 넓이를 출력해야 한다. 

1이 가로나 세로로 연결된 것을 "그림"이라고 하고, 1이 대각선으로 연결되어 있는 것은 서로 다른 그림이라도 한다. 

 

좀전에 배운 BFS를 떠올려보자. 

방문해야 하는 곳과 방문하지 않아야 할 곳이 표시된 판이 주어지고 (0,0)부터 시작해서 방문해야 하는 칸을 방문하고 표시를 남기고 했었다. 

 

이 문제를 다시 한번 보자. 

1로 이루어진 그림을 찾아야 한다. 마찬가지로 (0,0)부터 시작해서 1로 표시된 영역을 찾자. 

1로 표시된 영역을 찾았으면 그 영역에서 BFS를 진행하고 그 과정에서 넓이를 구하고 그림의 갯수를 +1해주면 된다. 

 

 

내 코드

namespace BFS
{
    internal class BOJ1926_그림
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        static string[] input1;
        static string[] input2;

        static int[,] board;
        static bool[,] vis;
        static int[] dx = { 1, 0, -1, 0 };
        static int[] dy = { 0, 1, 0, -1 };

        static Queue<(int x, int Y)> queue = new Queue<(int X, int Y)>();

        static void Main(string[] args)
        {
            input1 = sr.ReadLine().Split(" ");

            int n = int.Parse(input1[0]);
            int m = int.Parse(input1[1]);

            board = new int[n, m];
            vis = new bool[n, m];

            int count = 0;
            int area = 0;

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

            // board 초기화 
            for (int x = 0; x < n; x++)
            {
                input2 = sr.ReadLine().Split(" ");
                for(int y = 0; y < input2.Length; y++)
                {
                    board[x, y] = int.Parse(input2[y]);
                }
            }

            for(int x = 0; x < n; x++)
            {
                for(int y = 0; y < m; y++)
                {
                    if (board[x, y] == 1 && !vis[x, y]) 
                    {
                        // 방문 표시, 큐에 좌표 넣기. 
                        vis[x, y] = true;
                        queue.Enqueue((x, y));

                        // 그림 개수 늘리기.
                        count++;

                        // 넓이 계산
                        area++;

                        while(queue.Count > 0)
                        {
                            // front 빼기 
                            (int X, int Y) cur = queue.Dequeue();

                            // 상하좌우 확인 후, 큐에 넣기 (파란색 칸이면서 아직 방문하지 않았다면)
                            for (int dir = 0; dir < 4; dir++)
                            {
                                // 상하좌우 좌표 구하기. 
                                int nx = cur.X + dx[dir];
                                int ny = cur.Y + dy[dir];

                                // 인덱스 범위에서 벗어나거나, 이미 방문한 칸이거나, 빨강칸이면
                                // 다음 좌표 검사하기.
                                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                                if (vis[nx, ny] || board[nx, ny] != 1) continue;

                                vis[nx, ny] = true; // 방문했음을 표시
                                queue.Enqueue((nx, ny)); // 
                                area++;
                            }
                        }

                        areaList.Add(area);
                        area = 0;
                    }
                }
            }

            sw.WriteLine(count);

            if(areaList.Count != 0)
            {
                sw.WriteLine(areaList.Max());
            }
            else
            {
                sw.WriteLine(0);
            }

            sw.Close();
            sr.Close();
        }
    }
}

 

 

다른 사람 코드

namespace BFS
{
    internal class BOJ1926_그림
    {
        static int[,] board;
        static bool[,] vis;

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

        static Queue<(int x, int Y)> queue = new Queue<(int X, int Y)>();

        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        static string[] input1;
        static string[] input2;

        static void Main(string[] args)
        {
            input1 = sr.ReadLine().Split(" ");
            int n = int.Parse(input1[0]);
            int m = int.Parse(input1[1]);

            board = new int[n, m];
            vis = new bool[n, m];

            for(int x = 0; x < n; x++)
            {
                input2 = sr.ReadLine().Split(" ");
                for(int y = 0; y < m; y++)
                {
                    board[x, y] = int.Parse(input2[y]);
                }
            }

            int mx = 0; // 그림의 최댓값
            int num = 0; // 그림의 수

            for(int x = 0; x < n; x++)
            {
                for(int y = 0; y < m; y++)
                {
                    if (board[x, y] == 0 || vis[x, y]) 
                    {
                        continue;
                    }

                    num++;
                    vis[x, y] = true;
                    queue.Enqueue((x, y));

                    int area = 0;
                    while(queue.Count > 0)
                    {
                        area++;
                        (int X, int Y) cur = queue.Peek();
                        queue.Dequeue();

                        for(int dir = 0; dir < 4; dir++)
                        {
                            int nx = cur.X + dx[dir];
                            int ny = cur.Y + dy[dir];

                            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                            if (vis[nx, ny] || board[nx, ny] != 1) continue;

                            vis[nx, ny] = true;
                            queue.Enqueue((nx, ny));
                        }
                    }

                    mx = Math.Max(mx, area);
                }
            }

            sw.WriteLine(num);
            sw.WriteLine(mx);

            sw.Close();
            sr.Close();
        }
    }
}

 

코드의 순서만 다를뿐 전체적인 흐름은 똑같은 것 같다. 

 

 

복습1 풀이 (5/8)

BFS 문제다. (0,0)부터 시작해서 탐색가능한지 확인후 탐색가능하다면 BFS로 탐색하며 넓이를 계산하고 그림의 개수를 헤아리면 된다. 

 

 

복습1 코드1 - 오답

using System.Text;

namespace BFS
{
    internal class BOJ1926_그림_복습1
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static StringBuilder sb = new StringBuilder();

        static void Main(string[] args)
        {
            string[] input1 = sr.ReadLine().Split(" ");

            int n = int.Parse(input1[0]);
            int m = int.Parse(input1[1]);

            int[,] board = new int[n, m]; // [6,5]-> (0,0) ~ 
            bool[,] visit = new bool[n, m];

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

            for(int i = 0; i < board.GetLength(0); i++)
            {
                input1 = sr.ReadLine().Split(" ");
                for(int j = 0; j < board.GetLength(1); j++)
                {
                    board[i, j] = int.Parse(input1[j]);
                }
            }

            int count = 0;
            int maxWidth = -1;
            Queue<(int x, int y)> queue = new Queue<(int x, int y)>();
            for(int i = 0; i < board.GetLength(0); i++)
            {
                for(int j = 0; j < board.GetLength(1); j++)
                {
                    int width = 0;

                    if (board[i, j] != 0 && !visit[i, j])
                    {
                        // (i, j)를 탐색 
                        queue.Enqueue((i, j));
                        visit[i, j] = true;
                        width++;
                    }
                    else
                        continue;

                    while(queue.Count > 0)
                    {
                        (int x, int y) pos = queue.Dequeue();

                        // (i, j)의 상하좌우 좌표를 탐색
                        for(int dir = 0; dir < 4; dir++)
                        {
                            int posX = pos.x + dx[dir];
                            int posY = pos.y + dy[dir];

                            // (i, j)의 상하좌우 좌표가 인덱스 범위를 벗어나면 
                            if (posX < 0 || posX >= m-1 || posY < 0 || posY >= n-1)
                                continue; // 넘어가기. 

                            // 이미 방문한 좌표이거나, 방문할 수 없는 좌표이면 
                            if (visit[posX, posY] || board[posX, posY] == 0)
                                continue; // 넘어가기.

                            // 방문한적이 없는 좌표이거나, 방문할 수 있는 좌표이면 
                            visit[posX, posY] = true; // 방문표시
                            width++; // 넓이 계산
                            queue.Enqueue((posX, posY)); // 기준 좌표를 큐에 저장 
                        }
                    }

                    if (width > 0)
                        count++;

                    // bfs 끝
                    maxWidth = width > maxWidth ? width : maxWidth; // 최댓값 갱신 
                }
            }

            sb.AppendLine($"{count}");
            sb.AppendLine($"{maxWidth}");

            sw.WriteLine(sb.ToString());

            sw.Close();
            sr.Close();
        }
    }
}

상하좌우 좌표를 체크하는 posX와 posY 인덱스 범위 조건문을 잘못 설정했다. n이 x좌표, m이 y좌표 인덱스인데 반대로 생각했던 것 같다. 

 

 

복습1 코드2 - 정답

using System.Text;

namespace BFS
{
    internal class BOJ1926_그림_복습1
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static StringBuilder sb = new StringBuilder();

        static void Main(string[] args)
        {
            string[] input1 = sr.ReadLine().Split(" ");

            int n = int.Parse(input1[0]);
            int m = int.Parse(input1[1]);

            int[,] board = new int[n, m]; // [6,5]-> (0,0) ~ 
            bool[,] visit = new bool[n, m];

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

            for(int i = 0; i < board.GetLength(0); i++)
            {
                input1 = sr.ReadLine().Split(" ");
                for(int j = 0; j < board.GetLength(1); j++)
                {
                    board[i, j] = int.Parse(input1[j]);
                }
            }

            int count = 0;
            int maxWidth = -1;
            Queue<(int x, int y)> queue = new Queue<(int x, int y)>();
            for(int i = 0; i < board.GetLength(0); i++)
            {
                for(int j = 0; j < board.GetLength(1); j++)
                {
                    int width = 0;

                    if (board[i, j] != 0 && !visit[i, j])
                    {
                        // (i, j)를 탐색 
                        queue.Enqueue((i, j));
                        visit[i, j] = true;
                        width++;
                    }
                    else
                        continue;

                    while(queue.Count > 0)
                    {
                        (int x, int y) pos = queue.Dequeue();

                        // (i, j)의 상하좌우 좌표를 탐색
                        for(int dir = 0; dir < 4; dir++)
                        {
                            int posX = pos.x + dx[dir];
                            int posY = pos.y + dy[dir];

                            // (i, j)의 상하좌우 좌표가 인덱스 범위를 벗어나면 
                            if (posX < 0 || posX >= n || posY < 0 || posY >= m)
                                continue; // 넘어가기. 

                            // 이미 방문한 좌표이거나, 방문할 수 없는 좌표이면 
                            if (visit[posX, posY] || board[posX, posY] == 0)
                                continue; // 넘어가기.

                            // 방문한적이 없는 좌표이거나, 방문할 수 있는 좌표이면 
                            visit[posX, posY] = true; // 방문표시
                            width++; // 넓이 계산
                            queue.Enqueue((posX, posY)); // 기준 좌표를 큐에 저장 
                        }
                    }

                    if (width > 0)
                        count++;

                    // bfs 끝
                    maxWidth = width > maxWidth ? width : maxWidth; // 최댓값 갱신 
                }
            }

            sb.AppendLine($"{count}");
            sb.AppendLine($"{maxWidth}");

            sw.WriteLine(sb.ToString());

            sw.Close();
            sr.Close();
        }
    }
}

상하좌우 좌표를 체크하는 조건문을 수정해줬다.