ABOUT ME

CS공부하는 블로그

Today
Yesterday
Total
  • [백준] 2567번 색종이 - 2
    Algorithm Study/C , C++ 2021. 7. 28. 23:47

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

     

    2567번: 색종이 - 2

    가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록

    www.acmicpc.net

     

    문제

    가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오.

    예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다.

     

     

    입력

    첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다. 

     

    출력

    첫째 줄에 색종이가 붙은 검은 영역의 둘레의 길이를 출력한다.

     

     

    풀이

    전 색종이 문제의 응용이다.
    색종이 배치는 똑같이 하지만 둘레를 구할 방법을 생각하지 못했다. 둘레는 인접한 영역이 0인 좌표의 갯수이다.
    1x1크기의 종이라면 인접한 영역 4개가 모두 0이기 때문에 둘레는 4가 된다.

    board[r][c]의 좌표가 1인 경우에 4방향으로 체크하여 0이라면 둘레를 1 증가시키면 된다.

     

    전체 코드 

    #include<iostream>
    using namespace std;
     
    int main() {
     
        int board[101][101] = {0,};
        int N;
        int row, col;
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        int answer = 0;
     
        cin >> N;
        // 색종이 배치
        for (int i = 0; i < N; i++)
        {
            cin >> row >> col;
     
            for (int r = row; r < row + 10; r++)
                for (int c = col; c < col + 10; c++)
                    board[r][c] = 1;
        }
     
        for (int r = 1; r < 101; r++)
            for (int c = 1; c < 101; c++)
            {
                if(board[r][c] == 1)
                {
                    for (int i = 0; i < 4; i++)
                    {
                        if (board[r + dy[i]][c + dx[i]] == 0)
                            answer++;
                    }
                }
            }
     
     
        cout << answer;
     
        return 0;
    }

    'Algorithm Study > C , C++' 카테고리의 다른 글

    댓글

From BlackHair