[BOJ] #18428 감시피하기 , #11660 구간 합 구하기5, #18290 NM과 K (java)

#18428 감시피하기

문제로가기

문제이해

장애물, 선생님, 학생이 있고 장애물이 학생이 있는 row나 column에 있게 되면 선생님은 학생을 발견하지 못한다.

선생님이 상하좌우에서 학생을 발견한다면 no를, 발견하지 못한다면 yes를 출력

단 장애물은 3개까지 설치할 수 있다.

해결방법 고안

장애물을 설치하는 건 - dfs

선생님이 상하좌우에서 학생이 있는지 탐지하는 건 - bfs로 생각했다. 지금 생각해보면 bfs는 필요없는 듯 하긴 하다.

dfs로 장애물 3개를 추가한 map을 만든다 -> 그 map에서 바로 check 함수로 bfs를 호출한다.

check 함수에는 일단 선생님의 위치를 que에 넣어두고 그 위치에서 열과 행을 다 검사해서 학생을 발견하면 false를 하고, 장애물을 발견하면 반복문을 break하고 다른 행과 열을 검사한다. 끝까지 발견하지 못한다면 그 map은 true가 된다. true가 하나라도 있는 map 이 있다면 최종으로 yes를 출력하게 되는 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    static int deltas[][] = {{0, -1},{0,1}, {1, 0}, {-1, 0}};
    static String map[][];
    static int n;
    static int yes;
    static int no;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(input.readLine());
        map = new String[n][n];
        for(int i=0; i<n; i++) {
            tokens = new StringTokenizer(input.readLine());
            for(int j=0; j<n; j++){
                map[i][j] = tokens.nextToken();
            }

        }

        dfs(0);
        if(yes==0){
            System.out.println("NO");
        }
        else{
            System.out.println("YES");
        }
    }

    //장애물 3개 설치하는 함수
    private static void dfs(int count){
        //장애물 3개가 된다면
        if(count == 3){
            boolean flag = check(map); //학생 여부를 판단
            if(flag) yes++; //학생이 없다면 yes
            return;
        }
        else{
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(map[i][j].equals("X")){
                        map[i][j] = "O";
                        dfs(count+1);
                        map[i][j]="X";
                    }
                }
            }
        }
    }
    //행열에 선생님이 있는지 확인하는 함수
    private static boolean check(String[][] temp){
        Queue<int[]> que = new LinkedList<>();
        //선생님의 위치를 다 넣어둠
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(temp[i][j].equals("T")){
                    que.offer(new int[]{i,j});
                }
            }
        }
        //que가 비어있지 않을 때까지
        while(!que.isEmpty()){
            int t[] = que.poll();
            for(int d=0; d<4; d++){
                int x = t[0];
                int y = t[1];
                for(int i=0; i<n; i++){
                    x+= deltas[d][0];
                    y+= deltas[d][1];

                    int nx = x;
                    int ny = y;

                    if(nx >=0 && nx<n && ny >=0 && ny<n){
                        if(temp[nx][ny].equals("S")){
                            return false;
                        }
                        //해당 줄에 장애물 있으면 그 해당 줄 취소
                        if(temp[nx][ny].equals("O")){
                            break;
                        }
                    }
                }
            }
        }
        return true;
    }
}

#11660 구간 합 구하기

문제로가기

 

처음에 부분합으로 풀었다가 시간초과가 간 문제이다

이 문제는 누적합을 사용해야 한다.

문제이해

입력으로 주어지는 (x1,y1) 부터 (x2,y2)까지 누적합을 구해야 한다.

해결 방법 고안

1. 누적합을 저장하는 sum 배열을 만들어야 한다.

sum 배열에서 저장할 때는 그 위치값 + 그 row 전값의 합 + 그 col 전값의 합 그리고 row-1 col-1 값은 빼주어야 한다. 이 값은 겹치기 때문..!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

예를 들어서 36의 이 나오는 방법은 sum[2][4] = arr[2][4] + sum[1][3] + sum[2][3] - sum[1][3] 이다. 왼쪽 열과 오른쪽 열을 다 더한것이 24이고, 왼쪽 열을 다 더한 것이 10이니까 겹치는 부분 누적합이 6이므로 빼주는 것이다

 

2. sum 배열에 누적합을 다 저장했다면 원하는 누적합의 부분을 추출해야 한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이건 map 배열이라고 보면 [2][2]에서 [3][3]의 까지의 값을 구하고 싶다고 보자

그럼 sum[3][3]에서 -sum[1][3] - sum[3][1] 을 빼주고 마지막에 중복해서 빼주는 값 sum[1][1]을 더해주면 된다. 그럼 저 노란 부분이 나오게 된다

 

package boj;

import javax.swing.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj11660 {
    private static StringTokenizer tokens;
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {

        tokens = new StringTokenizer(input.readLine());
        int n = Integer.parseInt(tokens.nextToken());
        int m = Integer.parseInt(tokens.nextToken());
        int map[][] = new int[n+1][n+1];
        int sum[][] = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            tokens = new StringTokenizer(input.readLine());
            for(int j=1; j<=n; j++){
                map[i][j] = Integer.parseInt(tokens.nextToken());
                sum[i][j] = map[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }
        for(int i=0; i<m; i++){
            tokens = new StringTokenizer(input.readLine());
            int x1 = Integer.parseInt(tokens.nextToken());
            int y1 = Integer.parseInt(tokens.nextToken());
            int x2 = Integer.parseInt(tokens.nextToken());
            int y2 = Integer.parseInt(tokens.nextToken());

            int res = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
            System.out.println(res);
        }

    }
}

 

#18290 NM과 K

문제로 가기

문제 이해

N과M의 판에서 조합으로 K만큼 선택하고 그 선택한 수들의 최대합을 구해야 한다.

단, 인접한 배열이면 안된다.

 

해결 방법 고안

1. 배열로 만들지 않고 리스트를 만들어서 다 넣고 조합으로 고른다음 인접한 행열의 위치도 저장해주려고 했다

--> 실패. 인접한 행 열이니까 굳이 리스트로 X 더 복잡하다.

2. 2차원 배열을 1차원처럼 순회하는 방법을 배웠다.

int row = i/m, int col = i%m이다. m은 여기서 column의 수니까 row은 나눠주면 되고 column은 나머지 값으로 나온다.

그리고,  조합에서 굳이 배열로 후보를 만들지 않고 바로 최대값을 구하는 방법을 알았다.

처음에 리스트를 모두 구해서 그 리스트의 합을 다 더하려고 했는데 문제에서 주어진 것도 배열의 값이 아니라 최대값만 구하면 되니까,

배열 구하지 말고 그냥 최대값 구하기에만 집중해야 겠다.

 

코드는 아래에

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

public class Main {
    private static StringTokenizer tokens;
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static int n,m,k;
    private static int map[][]; //후보 배열
    private static boolean visited[][];
    private static int max_value = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        m = Integer.parseInt(tokens.nextToken());
        k = Integer.parseInt(tokens.nextToken());
        visited = new boolean[n][m];
        map = new int[n][m];
        for(int i=0; i<n; i++){
            tokens = new StringTokenizer(input.readLine());
            for(int j=0; j<m; j++){
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }
        //System.out.println(list);
        combi(0,0,0);
        System.out.println(max_value);
    }
    private static void combi(int start, int cnt, int currentSum){

        if(cnt >= k){
            max_value = Math.max(max_value, currentSum);
            return;
        }
        //2차원 배열을 1차원처럼
        for(int i = start; i<n*m; i++){
            int row = i/m; //현재 인덱스를 행으로 자르기
            int col = i%m;
            if(visited[row][col]) continue;
            //지금 인덱스에서 인접한 행이 아닌것
            if( col+1 < m && visited[row][col+1]
                    || row+1 <n && visited[row+1][col]
                    || col-1 >=0 && visited[row][col-1]
                    || row-1 >=0 && visited[row-1][col]) {
                continue;
            }
            visited[row][col] = true;
            combi(i+1, cnt+1, currentSum+map[row][col]);
            visited[row][col] = false;
        }
    }
}