[SWEA] 2117. 홈 방범 서비스

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

SW Expert Academy

이번에는 두 가지 방법으로 풀어보았다. 사실 첫 번째 풀이(BFS)로 풀고 다른 사람들 실행 시간과 비교해봤을때 엄청 빠르게 푼 사람이 있어서 다른 사람들 풀이 좀 찾아보고 다시 풀어봤다ㅠㅠ 두 번째 풀이가 훨씬 빠를 뿐만아니라 메모리 차이도 엄청나다...

 

 

두 번째 풀이

첫 번째 풀이

 

첫 번째 풀이 (BFS 풀이)

1. K 값이 커질 때마다 BFS가 단계별로 진행하는 모양과 같기 때문에 BFS로 풀었다.
2. N의 범위가 (5 ≤ N ≤ 20) 이므로 완전 탐색을 해줬다.
3. 모든 칸에 대해서 bfs를 통해 서비스 영역 모양 처럼 퍼지도록 계산해줬다.
4. K 값이 증가할때마다 서비스를 받는 집의 수를 계산하고 최댓값을 저장한다.
   1. K 값이 바뀌는 것은 큐 사이즈를 저장해놨다가 큐 사이즈 만큼을 진행해주고 나면된다.
   2. 예를 들어 K=1 일때 큐 size 는 1이고 K=2 일때 size는 4, K=4 일때 size = 8 이다.
   3. K 값이 바뀔 때마다 calc 함수에서 최대 서비스할 수 있는 집의 개수를 세서 리턴한다.

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

public class Solution {
	static class Pair {
		int x;
		int y;
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int N,M,max;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int[][] city;
	static Queue q = new LinkedList();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			city = new int[N][N];
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					city[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			max = 0;
            
            //모든칸 탐색
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					bfs(i,j);
				}
			}
			
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void bfs(int i, int j) {
		
		boolean check[][] = new boolean[N][N];
		q.add(new Pair(i,j));
		check[i][j] = true;
		int homecnt = 0;
		int k = 1;
		int size = q.size(); //처음 큐 사이즈 저장( 1값을 저장)
		while(!q.isEmpty()) {
			
			//K 값이 증가할 때마다 서비스를 받는 집의 수를 계산하고 최댓값을 저장한다.
			homecnt = calc(k++, check);
			if(max < homecnt) {
				max = homecnt;
			}
			
			size = q.size(); //단계별로 진행하기 위해서 매번 들어가있는 큐사이즈를 구해준다
			while(size-- > 0) { //size 만큼 탐색 진행
				Pair p = q.remove();
				int x = p.x;
				int y = p.y;

				int cnt = 0;
				for(int l=0; l<4; l++) {
					int nx = x+dx[l];
					int ny = y+dy[l];
					if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
					if(check[nx][ny]) continue;
					q.add(new Pair(nx,ny));
					check[nx][ny] = true;
					if(city[nx][ny] == 1) cnt+= 1;
				}
			}
			
			
		}
	}
	
	static int calc(int k, boolean[][] check) {
		int homecnt = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(check[i][j] && city[i][j] == 1) {
					homecnt += 1; //방문 한 곳(서비스 영역)중에 집이 있으면 집의 수를 count
				}
			}
		}
		
		int cost = (k*k)+((k-1)*(k-1));
		int profit = homecnt*M - cost;
		if(profit >= 0) //마이너스 값이 아닌 이상 손해가 아니다
			return homecnt;
		else
			return 0;
	}

}

 

 

두 번째 풀이

1. 모든칸에 대해서 K값에 따른 최대 집의 개수를 구해준다.
2. 집의 K값의 모양을 구하는식은
   1. 현재 칸이 x, y 라고 했을 때 모든 칸 i, j 에 대해서 계산해준다.
   2. K = |i-x| + |j-y|  를 계산해서 다음과 같이 구할 수 있다.
3. K=2 일때 위의 식을 사용하면 다음과 같이 된다.

		2
	2	1	2
2	1	(x,y)	1	2
	2	1	2
		2

 

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

public class Solution {

	static int N,M,max;
	static int[][] city;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			city = new int[N][N];
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					city[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			max = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					calc(i,j);
				}
			}
			
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void calc(int x, int y) {
        for (int k = 0; k < N + 2; k++) {
        	//K가 최대 N*N 칸을 모두 채우는 범위까지 진행
            int homecnt = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int nx = Math.abs(i - x);
                    int ny = Math.abs(j - y);
                    if (nx + ny < k && city[i][j] == 1) {
                    	//현재 K 일때의 서비스 영역이고, 집이 있으면 집의 수를 count 해준다.
                        homecnt++;
                    }
                }
            }
            int profit = (homecnt * M) - (k * k + (k - 1) * (k - 1)); //수익 계산
            if (profit < 0)
                continue;
            else
                max = Math.max(homecnt, max); //손해를 보지 않으면 집의 수를 최댓값과 비교하여 더 크면 저장.
        }
    }
	

}