SWEA[2117] - 홈 방범 서비스

링크

SWEA[2117]

문제설명

• BFS

문제풀이

• BFS + step 계산하면서 돈이랑 house 고려

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution2117 {

    public static int spend (int arange) {
        return arange*arange + (arange-1)*(arange-1);
    }

    public static int Ans;

    public static int N;
    public static int M;
    public static int[][] map;
    public static boolean[][] visit;
    public static int earned=0;
    public static int h_cnt=0;


    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static void BFS(int[] rc) {
        LinkedList<int[]> q = new LinkedList<>();
        visit[rc[0]][rc[1]]=true;
        q.add(new int[] {rc[0],rc[1]});
        int[] now;
        int qsize;
        int nr;
        int nc;
        int step=0;
        earned=0;
        h_cnt=0; 
        while(!q.isEmpty()) {
            qsize = q.size();
            step++;
            for (int i = 0; i < qsize; i++) {

                now = q.poll();
                if(map[now[0]][now[1]]==1) {
                    h_cnt++;
                    earned += M;
                }

                for (int d = 0; d < 4; d++) {
                    nr = now[0] + dir[d][0];
                    nc = now[1] + dir[d][1];
//                    경계 안이면
                    if(nr>=0 && nr<N && nc>=0 && nc<N && !visit[nr][nc]) {
                        visit[nr][nc]=true;
                        q.add(new int[] {nr,nc});
                    }
                }
            }
//            손해 안보는 경우
            if(spend(step)<=earned) {
                Ans = Math.max(Ans, h_cnt);
            }
//            손해 보는 경우
            else {
//                고려안함
            }
        }
    }

    public static void main(String args[]) throws IOException
    {
        System.setIn(new FileInputStream("res/swea/2117.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T;
        T=Integer.parseInt(br.readLine());
        for(int test_case = 1; test_case <= T; test_case++)
        {
//            입력
            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());
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    visit = new boolean[N][N];
                    BFS(new int[] {i,j});
                }
            }


            System.out.println("#"+test_case+" "+Ans);
//            초기화
            Ans=0;
        }//test_case end
    }//main end
}

아쉬운점

• 문제 제대로 안읽음(?) 테케보고 알았음
  • 영역의 중심이 집에서만 되는건 줄 알았음
• visit 처리 안해줬었음
  • BFS -> VISIT 처리 필수

잘한점

• BFS + 여러가지 변수 고려함