[SWEA] 2117.홈 방범 서비스 (java) / BFS 또는 List 활용

@BFS 또는 List 활용 / 50m

처음에 BFS로 풀었는데, List를 활용해서 푸는 코드가 훨씬 효율적이다.

BFS로 처음 풀 때 시간이 터지지 않을까 걱정했는데, 기우였다. BFS로만 풀어도 빠름

근데 List로 풀면 BFS 코드보다 시간이 반으로 준다.

 

문제 링크

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

SW Expert Academy

 

BFS 코드 구현 방법

1. 이중 for문으로 각 점을 돌면서, 각 점마다 bfs를 돈다.

 

2. bfs에서는 N + 1 만큼 for문을 돌면서(map의 길이가 짝수일 경우, N으로 하면 끝까지 안 도는 경우가 발생한다)

for문을 하나 더 써서 q.size()만큼 돌린다.

 

이렇게 하는 이유는, 가장자리에 한 줄을 추가할 때마다 비용과 손해 여부, 집의 개수를 체크하기 위해서이다.

첫 포문을 시작하고, 다음 포문을 시작하기 전에, 손해 여부를 체크하는 if문을 넣고 집의 개수를 갱신하는 코드를 넣어준다.

 

 

BFS를 활용한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_bfs {
	
	private static class Node {
		int x, y;
		Node (int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	private static int N, M, totalHouse, maxHouse, nowHouse, map[][];
	private static Queue<Node> q;
	private static boolean[][] visit;
	private static int[] dx = {0, -1, 0, 1}, dy = {1, 0, -1, 0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			q = new LinkedList<>();
			totalHouse = maxHouse = 0;
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (map[i][j] == 1) totalHouse++;
				}
			}
			startPoint();
			sb.append("#" + t + " " + maxHouse + "\n");
		}
		System.out.println(sb);
	}

	private static void startPoint() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				nowHouse = (map[i][j] == 1) ? 1 : 0;
				q.clear();
				visit = new boolean[N][N];
				visit[i][j] = true;
				q.add(new Node(i, j));
				bfs();
			}
		}
	}

	private static void bfs() {
		int nowCost = 1;
		for (int idx = 1; idx <= N + 1; idx++) {
			nowCost += (idx - 1) * 4;
			
			if (nowHouse > 0) {
				if ((nowHouse * M) - nowCost >= 0) {
					if (maxHouse < nowHouse)
						maxHouse = nowHouse;
					
					if (maxHouse == totalHouse)
						return;
				}
			}
			
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Node temp = q.poll();
				
				for (int d = 0; d < 4; d++) {
					int nx = temp.x + dx[d];
					int ny = temp.y + dy[d];
					if (nx < 0 || nx >= N || ny < 0 || ny >= N || visit[nx][ny]) continue;

					if (map[nx][ny] == 1) nowHouse++;
					visit[nx][ny] = true;
					q.add(new Node(nx, ny));
				}
			}
		}
	}
}

 

 

List를 활용한 코드 구현 방법

이 방법으로 풀면 맵도, visit도 다 필요 없어서 메모리 사용량이 작아지고, BFS로 불필요한 작업(visit체크, visit확인, 집이 없는 곳에 체크 등)을 하지 않아서 시간도 굉장히 빨라진다.

시작점부터 다른 집들간의 거리만 구해주면 되므로 굉장히 효율적인 코드이다.

 

1. 일단 이중 포문으로 맵을 돌면서 시작점을 찾는 부분까지는 BFS 코드와 동일하다.

 

2. 1번에서 찾은 시작점을 기준으로, 이중 for문을 돌린다.

바깥 for문은 N + 1 만큼 돌리고, (길이)

내부 for문은 list.size()만큼 for문을 돌리면서 (지금 점과 list에서 빼낸 점의 거리 == 바깥 for문의 길이) 가 성립하면 집의 개수를 카운트 해준다.

 

이 때도 바깥 for문과 내부 for문 사이에 손해 여부와 집의 개수를 체크하는 부분이 필요하다. 그런데 이때는 거리가 0부터 시작하므로 내부 for문 밑에 해당 코드를 넣어줘야 한다.

 

 

 

List를 활용한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_list {
	
	private static class Node {
		int x, y;
		Node (int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	private static int N, M, totalHouse, maxHouse, nowHouse;
	private static ArrayList<Node> list;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			maxHouse = 0;
			list = new ArrayList<>();
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++)
					if (Integer.parseInt(st.nextToken()) == 1)
						list.add(new Node(i, j));
			}
			
			totalHouse = list.size();
			startPoint();
			sb.append("#" + t + " " + maxHouse + "\n");
		}
		System.out.println(sb);
	}

	private static void startPoint() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				nowHouse = 0;
				getHouseNum(i, j);
			}
		}
	}

	private static void getHouseNum(int x, int y) {
		int nowCost = 1;
		for (int dist = 0; dist <= N ; dist++) {
			nowCost += dist * 4;
			
			for (int i = 0; i < list.size(); i++)
				if (Math.abs(list.get(i).x - x) + Math.abs(list.get(i).y - y) == dist)
					nowHouse++;

			if (nowHouse > 0) {
				if ((nowHouse * M) - nowCost >= 0) {
					if (maxHouse < nowHouse)
						maxHouse = nowHouse;
					
					if (maxHouse == totalHouse)
						return;
				}
			}
		}
	}
}

 

 

아래가 BFS로 푼 코드, 위가 List로 푼 코드이다.

무난한 난이도로 재밌게 풀었다.

 

끝!