[백준] 색종이-2 2567번 (PYTHON,JAVA)

✔ 문제 2567 색종이-2

문제 바로가기 💨 

2567번: 색종이 - 2

핵심 아이디어

먼저 2차원배열에 1로 색종이를 표시한다. 둘레 탐색은 두가지 방법이 있다. 

1. 전체순회를 하며, 1을 만나면 해당 위치를 기준으로 4방향을 탐색해 0의 개수를 센다.

2. 함수를 가로,세로 방향으로 쭉 탐색하며 0>1,1>0 이 바뀌는 경계개수를 센다.

풀이에선 두번째 방법을 이용했다.

 

+) 파이썬에서 전치를 할때는 zip(*list)를 이용했다. 예를들어, [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] list를 *로 unpacking 해주게 되면 [1, 2, 3], [4, 5, 6], [7, 8, 9] 3개의 iterable한 자료형이 된다. zip은 이 자료형을 index끼리 묶어 반환하게 된다.

---

PYTHON

def count(arr):
    cnt = 0
    for lst in arr:
        for i in range(1, len(lst)):
            if lst[i-1] != lst[i]: # 현재값과 직전의 값이 다르면 경계선!
                cnt+=1
    return cnt

N = int(input())
arr = [[0]*102 for _ in range(102)]
for _ in range(N):
    # 해당영역을 1로 표시
    sj, si = map(int, input().split())
    for i in range(si, si+10):
        for j in range(sj, sj+10):
            arr[i][j] = 1
arr_t = list(zip(*arr)) # 전치행렬: 수정필요시 list(map(list, zip(*arr)))
ans = count(arr) + count(arr_t)
            
print(ans)

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] arr = new int[102][102];
        for (int k = 0; k < N; k++) {
            StringTokenizer tokenizer = new StringTokenizer(br.readLine());
            int sj = Integer.parseInt(tokenizer.nextToken());
            int si = Integer.parseInt(tokenizer.nextToken());

            for (int i = si; i < si + 10; i++) {
                for (int j = sj; j < sj + 10; j++) {
                    arr[i][j] = 1;
                }
            }
        }

        int[][] arr_t = transpose(arr);

        int ans = count(arr) + count(arr_t);
        System.out.println(ans);
    }

    private static int[][] transpose(int[][] arr) {
        int rows = arr.length;
        int cols = arr[0].length;

        int[][] transposed = new int[cols][rows];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                transposed[j][i] = arr[i][j];
            }
        }
        return transposed;
    }

    private static int count(int[][] arr) {
        int cnt = 0;

        for (int[] lst : arr) {
            for (int i = 1; i < lst.length; i++) {
                if (lst[i - 1] != lst[i]) {
                    cnt += 1;
                }
            }
        }
        return cnt;
    }
}