문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

코드 (Java)

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

class Solution
{
	private static final int ROW = 0;
	private static final int COL = 1;
	private static final int K = 2;
	private static final int[][] delta = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
	
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T = Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			//obtain data
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			//make a map
			boolean[][] houses = new boolean[N][N];
			for (int row = 0; row < N; ++row ) {
				st = new StringTokenizer(br.readLine());
				for (int col = 0; col < N; ++col) {
					if (Integer.parseInt(st.nextToken()) == 1) {
						houses[row][col] = true;
					}
				}
			}
			
//			for (int row = 0; row < N; ++row) {
//				for (int col = 0; col < N; ++col) {
//					if (houses[row][col]) {
//						System.out.print("1 ");
//					} else System.out.print("0 ");
//				}
//				System.out.print("\n");
//			}
			
			//bruteforce for each map position
			int maxHouse = 0;
			for (int row = 0; row < N; ++row) {
				for (int col = 0; col < N; ++col) {
					//we do bfs for searching.
					//first, we do some basic setup
					boolean[][] visited = new boolean[N][N];
					Queue<int[]> q = new LinkedList<>();
					visited[row][col] = true;
					q.add(new int[] {row, col, 1});
					int curK = 1; //for tracking which K are we counting for.
					int curHouse = 0;
					
					while (!q.isEmpty()) {
						int[] curNode = q.poll();
//						bw.write(curNode[0] + " " + curNode[1] + " " + curNode[K] + "\n");
						
						//calculate statistics
						if (curNode[K] > curK) {
							//calculate current statistics about K.
							int cost = curK*curK + (curK-1)*(curK-1);
							int income = curHouse * M;
							if (income >= cost) {
								maxHouse = Math.max(maxHouse, curHouse);
							}
							curK++;
						}
						
						//calculate coverd house for curK
						if (houses[curNode[ROW]][curNode[COL]]) {
							curHouse++;
						}
						
						//next iteration setup
						for (int idx = 0; idx < 4; ++idx) {
							int newR = curNode[ROW] + delta[idx][ROW];
							int newC = curNode[COL] + delta[idx][COL];
							if (newR >= 0 && newR < N && newC >= 0 && newC < N && !visited[newR][newC]) {
								visited[newR][newC] = true;
								q.add(new int[] {newR, newC, curNode[K]+1});
							}
							
						}
					}
					
					int cost = curK*curK + (curK-1)*(curK-1);
					int income = curHouse * M;
					if (income >= cost) {
						maxHouse = Math.max(maxHouse, curHouse);
					}
				}
			}
			
			bw.write("#" + test_case + " " + maxHouse + "\n");
			bw.flush();
		}
//		bw.flush();
		bw.close();
		br.close();
	}
}

풀이

• 무지성 BFS로 풀었다.

• 메모리적으로 효율적이지 않고 시간도 오래걸렸는데, 실제로 다시보니 무지성으로 BFS를 하기보다는, 마름모를 미리 만들어가지고 이리저리 옮겨가지고 탐색하는것이 더 효율적일것 같긴하다. 뭐 제약조건 고려해가지고 시간안에 될걸 알고 위처럼 구현한거긴하지만 여튼.

• 또 유의해야하는게, 위처럼 BFS가 끝난 후에도 한번 더 집을 최대로 사용할 수 있는지에 대한 검산이 필요하다. 안 그러면 특정 경우에 대해서 (지도를 그냥 전부 덮는 경우에 대해서) 고려를 하지 못하기 때문.