SWEA 2117. [모의 SW 역량테스트] 홈 방범 서비스

Link

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=%EC%97%AD%EB%9F%89&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

---

 

내가 제출한 코드

import org.w3c.dom.ls.LSOutput;

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int answer, n, m;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] map;
    static boolean[][] v;

    public static void main(String[] args) throws Exception {
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            init();
            run();
            sb.append("#").append(i + 1).append(" ").append(answer).append("\n");
        }
        System.out.println(sb);
    }

    private static void init() throws Exception {
        // 정답 초기화
        answer = Integer.MIN_VALUE;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        map = new int[n][n];

        m = Integer.parseInt(st.nextToken());

        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());
            }
        }
    }

    private static void run() {
        // 모든 좌표에서 확인
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                bfs(i, j);
            }
        }
    }

    private static void bfs(int x, int y) {
        // Max K = n+1 ( 홀수, 짝수 경우를 고려 )
        for (int i = 1; i <= n+1; i++) {
            
            Deque<int[]> q = new ArrayDeque<>();
            v = new boolean[n][n];
            // 수입
            int totalCost = 0;
            // 집 수
            int homeCnt = 0;
            // x, y, len
            q.add(new int[]{x, y, 0});
            v[x][y] = true;

            while (!q.isEmpty()) {
                int[] cur = q.poll();
                
                // 현재 K의 범위 = i
                if (cur[2] == i) continue;
                
                // 집이 있는 경우
                if (map[cur[0]][cur[1]] == 1) {
                    homeCnt++;
                    totalCost += map[cur[0]][cur[1]] * m;
                }

                for (int j = 0; j < 4; j++) {
                    int nx = cur[0] + dx[j];
                    int ny = cur[1] + dy[j];
                    
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n || v[nx][ny]) continue;

                    v[nx][ny] = true;
                    q.add(new int[]{nx, ny, cur[2] + 1});
                }
            }
            
            // 이득을 보면서 집 수가 더 많은 경우
            if (answer < homeCnt && 0 <= totalCost - ((i * i) + (i - 1) * (i - 1))) {
                answer = homeCnt;
            }
        }
    }

}

---

 

로직

1. 모든 좌표에서 탐색을 진행

2. K의 범위를 N의 값보다 1 크게 세팅 ( 홀수, 짝수의 경우에 값이 달라짐 )

3. 손해를 안보면서 ( totalCost >= 0 ) 집이 제일 큰 경우를 찾기

---