[Baekjoon] 9400_Calculate the Fence Needed

문제(출처: https://www.acmicpc.net/problem/9400)

---

< Calculate the Fence Needed >

 

문제 풀이 

 

한 격자 칸에 필요한 울타리의 길이 = 4 - (농장의 한 격자 칸과 연결된 농장의 격자 칸의 수)

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _9400_ { // Calculate the Fence Needed

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int N = 0;
		Queue<int[]> queue = new LinkedList<>();

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

		while ((N = Integer.parseInt(bf.readLine())) != 0) {
			boolean arr[][] = new boolean[101][101];

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(bf.readLine());

				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());

				arr[101 - x][y] = true;
				queue.add(new int[] { 101 - x, y });
			}

			int result = 0;
			while (!queue.isEmpty()) {
				int temp[] = queue.poll();
				int cnt = 0;

				for (int i = 0; i < 4; i++) {
					int x = temp[0] + dx[i];
					int y = temp[1] + dy[i];

					if (x >= 0 && x < 101 && y >= 0 && y < 101 && arr[x][y]) {
						cnt += 1;
					}
				}
				result += (4 - cnt);
			}
			bw.write(result + "\n");
		}
		bw.flush();
	}
}

변수)
N : 농장 면적
queue : Queue <int []>
dx, dy : 상, 하, 좌, 우
arr : 농장
result : 필요한 울타리 길이
cnt : 농장의 한 격자 칸과 연결된 농장의 격자 칸의 수

 

농장 면적을 입력받는다. 농장 면적만큼 좌표를 입력받아 배열 arr에 표시하고 queue에 저장한다. queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

2) 상, 하, 좌, 우를 탐색하며 농장인지 확인

3) 필요한 울타리 길이에 (4- 농장의 한 격자 칸과 연결된 농장의 격자 칸의 수) 더하기

 

최종 result를 출력한다.

---

---