SWEA : Day 3 (Java)

본 포스팅에서는 [활주로,  홈 방법서비스, 등산로 조성, 벌꿀채취]를 다룹니다.

4014. (모의 SW) 활주로

import java.io.*;
import java.util.*;
public class Solution {
    // 활주로는 높이가 동일한 구간에서 건설
    // 높이가 다른 경우 경사로를 설치
    static int N, X; // 맵크기, 경사로 높이
    static int map[][];
    static boolean visited[][];
    static int ans;
    static StringBuilder sb = new StringBuilder();
 
    // 건설
    static void construction() {
        visited = new boolean[N][N];
        boolean success;
        // 가로
        int r, c;
        for (r = 0; r < N; r++) {
            success = true;
            for (c = 1; c < N; c++) {
                if(Math.abs(map[r][c - 1] - map[r][c]) > 1) {
                    success = false;
                    break;
                }
                if (map[r][c - 1] == map[r][c])
                    continue;
                if (visited[r][c] == true) // 이미 건설됨
                    continue;
                // 전이 더 높다
                if (map[r][c - 1] > map[r][c]) {
                    visited[r][c] = true;
                    for (int d = 1; d < X; d++) {
                        int nc = c + d;
                        if (nc >= N || visited[r][nc] == true || map[r][c] != map[r][nc]) {
                            success = false;
                            break;
                        }
                        visited[r][nc] = true;
                    }
                } else { // 전이 더 낮다
                    visited[r][c - 1] = true;
                    for (int d = 1; d < X; d++) {
                        int nc = c - 1 - d;
                        if (nc < 0 || visited[r][nc] == true || map[r][c - 1] != map[r][nc]) {
                            success = false;
                            break;
                        }
                        visited[r][nc] = true;
                    }
                }
                if (!success) // 해당 행 실패
                    break;
            }
            if (success)
                ans++;
        }
        visited = new boolean[N][N];
        // 세로
        for (c = 0; c < N; c++) {
            success = true;
            for (r = 1; r < N; r++) {
                if(Math.abs(map[r-1][c] - map[r][c]) > 1) {
                    success = false;
                    break;
                }
                if (map[r - 1][c] == map[r][c])
                    continue;
                if (visited[r][c] == true) // 이미 건설됨
                    continue;
                // 전이 더 높다
                if (map[r - 1][c] > map[r][c]) {
                    visited[r][c] = true;
                    for (int d = 1; d < X; d++) {
                        int nr = r + d;
                        if (nr >= N || visited[nr][c] == true || map[r][c] != map[nr][c]) {
                            success = false;
                            break;
                        }
                        visited[nr][c] = true;
                    }
                } else { // 전이 더 낮다
                    visited[r - 1][c] = true;
                    for (int d = 1; d < X; d++) {
                        int nr = r - d - 1;
                        if (nr < 0 || visited[nr][c] == true || map[r - 1][c] != map[nr][c]) {
                            success = false;
                            break;
                        }
                        visited[nr][c] = true;
                    }
                }
                if (!success) // 해당 행 실패
                    break;
            }
            if (success)
                ans++;
        }
        sb.append(ans).append("\n");
        ans = 0;
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            X = 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());
                }
            }
            construction();
 
        }
        System.out.println(sb.toString());
    }
}

높이가 다른 경우 경사로를 설치할 수 있다. 가로랑 세로를 따로 나누어서 구현해주었다.

1) 가로

바로 직전 값과 비교를 하여 차이가 1 넘게 난다면 활주로를 설치해도 해결되지 않으므로 실패로 간주한 후 끝낸다. 만약 직전값이 더 높다면 내 칸부터 X까지 이동하면서 경사가 똑같은지 확인하고 visited로 이미 설치된 건 아닌지 확인한다. 만약 전이 더 낮다면 그 전값부터 X칸까지 경사가 똑같은지 확인하고 이미 설치된건 아닌지 확인한다. 

2) 세로

세로의 경우도 동일하다. 바로 직전값에 따라 코드를 구현하였다. 

 

이를 통해 가로, 세로에서 success한 행과 열을 확인하고 개수를 출력하게 된다

 

 

 

2117. (모의 SW) 홈 방범 서비스

import java.io.*;
import java.util.*;
public class Solution {
    static int N, M;
    static int map[][];
    static boolean visited[][];
    static final int dx[] = { -1, 1, 0, 0 };
    static final int dy[] = { 0, 0, -1, 1 };
    static int maxH, maxK;
    static int[] homeC;
 
    static class Pair {
        int first;
        int second;
        int cnt;
 
        Pair(int first, int second, int cnt) {
            this.first = first;
            this.second = second;
            this.cnt = cnt;
        }
    }
 
    static void findHouse(int r, int c) {
        int cntChange = 1;
        // 한계는 N+1이고 변하면 앞에꺼가져와야함
        homeC = new int[N + 2];
        int home = 0;
        Queue<Pair> q = new ArrayDeque<>();
        q.offer(new Pair(r, c, 1));
        visited = new boolean[N][N];
        visited[r][c] = true;
        int x, y, cnt;
        while (!q.isEmpty()) {
            x = q.peek().first;
            y = q.peek().second;
            cnt = q.peek().cnt;
            q.poll();
 
            if (cnt != cntChange) {
                homeC[cnt] = homeC[cntChange];
                cntChange = cnt;
            }
 
            if (map[x][y] == 1) {
                homeC[cnt]++;
            }
            if (cnt >= N + 1) // 한계
                continue;
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;
                if (visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                q.offer(new Pair(nx, ny, cnt + 1));
            }
        }
        for (int i = 1; i < N + 2; i++) {
            int op = (i * i) + (i - 1) * (i - 1);
            if ((M * homeC[i]) - op >= 0) {
                if (maxH < homeC[i]) {
                    maxH = homeC[i];
                }
            }
        }
 
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");
 
            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++) {
                    findHouse(i, j);
                }
            }
            sb.append(maxH).append("\n");
            maxH = 0;
        }
        System.out.println(sb.toString());
    }
}

BFS를 이용해서 점점 범위가 커지도록 설정을 해주었다. 같은 깊이인지 확인을 해주어야 하기 때문에 cntChange를 해줘서 지금 범위까지의 값을 저장해주었다. cnt로 넘겨주는 값이 같은 깊이인지 확인하는 값이다. x, y로 모든 좌료를 넘겨주고 max 값을 찾게 된다.

 

 

 

1949. (모의SW) 등산로 조성

import java.io.*;
import java.util.*;
public class Solution {
    static int N, K;
    static int map[][];
    static int maxH;
    static ArrayList<int[]> list;
    static final int dx[] = { -1, 0, 1, 0 };
    static final int dy[] = { 0, 1, 0, -1 };
    static boolean visited[][];
    static boolean cut;
    static int ans;
 
    static void construction(int x, int y, int cnt) {
        ans = Math.max(ans, cnt);
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                continue;
            if (visited[nx][ny])
                continue;
            visited[nx][ny] = true;
            if (map[x][y] > map[nx][ny])
                construction(nx, ny, cnt + 1);
            else if (cut == false && map[nx][ny] - K < map[x][y]) {
                cut = true;
                for (int i = 1; i < K + 1; i++) {
                    if (map[x][y] <= map[nx][ny] - i)
                        continue;
                    map[nx][ny] -= i;
                    construction(nx, ny, cnt + 1);
                    map[nx][ny] += i;
                }
                cut = false;
            }
            visited[nx][ny] = false;
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            visited = new boolean[N][N];
            list = new ArrayList<>();
            ans = 0;
            maxH = 0;
            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 (maxH < map[i][j]) {
                        maxH = map[i][j];
                        list.clear();
                        list.add(new int[] { i, j });
                    } else if (maxH == map[i][j]) {
                        list.add(new int[] { i, j });
                    }
                }
            }
 
            for (int i = 0; i < list.size(); i++) {
                int x = list.get(i)[0];
                int y = list.get(i)[1];
                visited[x][y] = true;
                construction(x, y, 1);
                visited[x][y] = false;
            }
            sb.append(ans).append("\n");
 
        }
        System.out.println(sb.toString());
    }
}

최고값에서 작은 값으로 이동하게 되는데, 작은값에서 큰 곳으로 가기 위해서는 설치를 진행해본다. 설치는 cut으로 판단을 한다. visited를 통해 왔던 곳을 가지 않도록 한다.

 

 

벌꿀채취는 추후 추가 예정