[구름톤챌린지] 7일차 구름 찾기 깃발

[구름톤챌린지] 

문제 # https://level.goorm.io/exam/195689/%EA%B5%AC%EB%A6%84-%EC%B0%BE%EA%B8%B0-%EA%B9%83%EB%B0%9C/quiz/1

 

 

임의의 칸에서 8방향의 인접한 칸을 탐색하여, 인접한 칸들 중 구름이 있는 칸의 개수를 저장하고 주어진 값`K`와 동일한 값을 칸의 개수로 가지는 칸이 몇 개가 존재하는지 구하는 문제

 

 

내가 작성한 코드

import java.io.*;
import java.util.*;

class Main {
	static final int DIR_NUM = 8;
	static int[] dy = {-1, -1, -1, 0, 1, 1, 1, 0};
	static int[] dx = {-1, 0, 1, 1, 1, 0, -1, -1};
	static int N, K; // 크기, 깃발 값
	
	static int[][] board;
	static int[][] flags;
	
	static int ans;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		K = Integer.parseInt(input[1]);
		
		board = new int[N][N];
		flags = new int[N][N];
		
		for(int y=0; y<N; ++y){
			input = br.readLine().split(" ");
			for(int x=0; x<N; ++x){
				board[y][x] = Integer.parseInt(input[x]);
			}
		}
		
		for(int y=0; y<N; ++y){
			for(int x=0; x<N; ++x){
				flags[y][x] = findFlagsValue(y, x);
				if(flags[y][x] == K) ans++;
			}
		}
		
		sb.append(ans);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
		
	}
	
	static int findFlagsValue(int y, int x){
		int cnt = 0;
		
		if(board[y][x] == 1){
			return cnt;
		}
		
		for(int i=0; i<DIR_NUM; ++i){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(!inRange(ny, nx)) continue;
			if(board[ny][nx]==0) continue;
			++cnt;
		}
		
		return cnt;
		
	}
	static boolean inRange(int y, int x){
		return 0<=y && y<N && 0<=x && x<N;
	}
}

 

풀이 및 배운 점

칸을 옮겨 인접한 곳의 깃발 개수를 계속 계산하는 문제지만, 겹치는 부분을 계속 구해야하기 때문에 이 부분을 새로 구하는 것은 비효율적이라고 생각하였다.

지금 푼 방식은 겹치는 부분도 다시 계산하는 비효율적인 방식이다.

 

입력을 모두 받아 2차원 배열 `board[][]`에 저장한다. 

반복문을 돌면서 각 8방향에서 구름이 있는지 확인한 후, 구름의 개수를 리턴해주는 메소드인`findFlagsValue(y, x)`를 호출하여 `flags[y][x]`에 저장해준다. 

 

이후, `K`값과 비교하여 같다면 `ans`값을 1 증가시켜준다.

 

그래서 2차원 배열에서 구간의 합으로 생각하여 `투포인터`와 `슬라이딩 윈도우` 로 풀 수 있을 것 같은데..라는 생각에 두 개념에 대해 공부해보고, 다시 풀어보려고 한다.

 

글을 작성하며 발견한 부분

1. findFlagsValue 메소드를 호출하기 전, board[y][x] 값을 확인하여 continue; 하면 스택에 메소드 호출이 쌓이지 않음

2. flags[y][x]는 재사용하지 않으므로, findFlagsValue의 리턴값과 K값을 바로 비교해줄 수도 있음

 

과 같이 내가 작성한 코드를 보면서 그냥 넘길 수 있었던, 보완할 수 있는 부분들을 다시 보며 깨달을 수 있어서 부족함을 다시 한 번 느낄 수 있는 시간이 되는 것 같다.