Programmers - 미로탈출 159993번

https://school.programmers.co.kr/learn/courses/30/lessons/159993

기본적인 길찾기 문제라고 생각했다.

1. 시작지점 -> 레버
2. 레버 -> 출구

이렇게 두번의 탐색을 실행하고, 둘중에 하나라도 못찾을 시 -1 return

Queue 를 활용한 bfs를 이용하여 문제를 풀이했다

마지막에 -2를 하고 return 하는 이유는 check 배열에서 이미 지나간 곳인지 체크할 때 0 인지 아닌지로 체크를 하는데, 처음 시작장소를 다시오면 안되므로 출발하는 장소의 check에 1를 넣고 시작했기 때문..

2차원 check배열은 출발지점으로부터 얼만큼 이동했는지 확인할 수 있는 저장장소이며, 이미 지나간 곳인지 확인할 수 있는 역할도 함.

​x
import java.util.LinkedList;
import java.util.Queue;

public class Programmers_159993 {

    final int MAX_MAP_SIZE = 101;

    Coordinate s = new Coordinate();
    Coordinate e = new Coordinate();
    Coordinate l = new Coordinate();

    int[][] map = new int[MAX_MAP_SIZE][MAX_MAP_SIZE];
    int[][] check;

    int[] dir_y = {-1,0,1,0};
    int[] dir_x = {0,1,0,-1};

    int map_height;
    int map_width;

    public int solution(String[] maps) {

        createMap(maps);
        map_height = maps.length;
        map_width = maps[0].length();

        int res1 = bfs(s.y, s.x, l.y, l.x);

        int res2 = bfs(l.y, l.x, e.y, e.x);

        if(res1 == 0 || res2 == 0)
            return -1;

        return res1 + res2 - 2;
    }

    int bfs(int start_y, int start_x, int end_y, int end_x) {

        check = new int[MAX_MAP_SIZE][MAX_MAP_SIZE];

        Queue<Coordinate> q = new LinkedList<>();
        q.add(new Coordinate(start_y,start_x));

        int idx = 1;

        check[start_y][start_x] = idx;

        while(q.size() != 0) {
            int y = q.peek().y;
            int x = q.poll().x;

            for(int i = 0; i < 4; i ++) {
                int next_y = y + dir_y[i];
                int next_x = x + dir_x[i];

                if(next_y < 0 || next_x < 0 || next_y >= map_height || next_x >= map_width)
                    continue;

                if(map[next_y][next_x] == 1 || check[next_y][next_x] != 0)
                    continue;

                check[next_y][next_x] = check[y][x] + 1;
                q.add(new Coordinate(next_y,next_x));
            }
        }

        if(check[end_y][end_x] != 0)
            return check[end_y][end_x];
        else
            return 0;
    }

    void createMap(String[] maps) {
        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {
                String tmp = maps[i].substring(j, j+1);
                if(tmp.equals("X"))
                    map[i][j] = 1;
                else if(tmp.equals("S")) {
                    s.y = i;
                    s.x = j;
                }
                else if(tmp.equals("L")) {
                    l.y = i;
                    l.x = j;
                }
                else if(tmp.equals("E")) {
                    e.y = i;
                    e.x = j;
                }
            }
        }
    }

    class Coordinate {
        int y;
        int x;

        Coordinate() { }
        Coordinate(int y,int x) {
            this.y = y;
            this.x = x;
        }
    }
}

Programmers - 무인도 여행 154540번

https://school.programmers.co.kr/learn/courses/30/lessons/154540

제한사항 이 부담이 없으므로 전체탐색을 통해 한번 쫘악 훑어 주면 될거 같다.

Queue를 활용한 bfs(너비우선탐색) 을 이용하여 문제를 풀었다.

이때 point가 약간 혼란스러울 수 있는데, 내가 생각한 y좌표는 height 높이라고 생각했고,

x좌표는 width 너비를 생각하여 문제를 풀이했는데 point 에서 제공하는 y와 x는 그 반대여서

Queue에 add할때 반대로 넣은걸 볼 수 있는데, 다음엔 다른걸 사용하여 이런 귀찮은 일을 없애야 겠다.

그리고 보면 문제에 비해 소스가 이상하게 좀 긴 느낌인데 쓸때 없는 부분을 정리해서 다시 짜 봐야겠음

xxxxxxxxxx

import java.awt.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Programmers_154540 {

    final int MAX_ISLAND_SIZE = 101;
    int[][] island = new int[MAX_ISLAND_SIZE][MAX_ISLAND_SIZE];
    int[][] check = new int[MAX_ISLAND_SIZE][MAX_ISLAND_SIZE];

    // 12시 부터 시계방향 검사
    int[] dir_y = {-1,0,1,0};
    int[] dir_x = {0,1,0,-1};

    public int[] solution(String[] maps) {
        ArrayList<Integer> res = new ArrayList<>();

        island = createIsland(maps);

        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {

                if(island[i][j] != 0 && check[i][j] == 0) {
                    res.add(bfs(i, j));
                }
            }
        }

        if(res.size() == 0) {
            res.add(-1);

            return res.stream()
                    .mapToInt(Integer::intValue)
                    .toArray();
        }

        Collections.sort(res);

        return res.stream()
                .mapToInt(Integer::intValue)
                .toArray();
    }

    int bfs(int y, int x) {

        Queue<Point> q = new LinkedList<>();
        int result = 0;

        // 체크안한 땅이고, 섬이면 진행
        if(check[y][x] != 1 && island[y][x] != 0) {
            q.add(new Point(x,y));
            check[y][x] = 1;
            result += island[y][x];
        }

        while(q.size() != 0) {
            int island_y = q.peek().y;
            int island_x = q.poll().x;

            // 4방향 검사
            for(int i = 0; i < 4; i++) {
                int next_island_y = island_y + dir_y[i];
                int next_island_x = island_x + dir_x[i];

                if(next_island_y < 0 || next_island_x < 0)
                    continue;

                if(check[next_island_y][next_island_x] != 0)
                    continue;

                if(island[next_island_y][next_island_x] == 0)
                    continue;

                result += island[next_island_y][next_island_x];
                check[next_island_y][next_island_x] = 1;
                q.add(new Point(next_island_x, next_island_y));
            }
        }

        return result;
    }

    int[][] createIsland(String[] maps) {
        int[][] result = new int[MAX_ISLAND_SIZE][MAX_ISLAND_SIZE];

        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {
                String tmp = maps[i].substring(j, j+1);
                if(tmp.equals("X"))
                    result[i][j] = 0;
                else
                    result[i][j] = Integer.parseInt(tmp);
            }
        }
        return result;
    }
}

Programmers - 호텔 대실 155651번

https://school.programmers.co.kr/learn/courses/30/lessons/155651

이 문제는 데이터 사이즈가 작아서 시간복잡도를 생각 안해도 될거 같았다.

그래서 처음엔 재귀를 사용해서 풀었는데, 누적합을 사용해서 푸는 방법이 있어서

해당 방법을 이용해 보았다.

시간은 계산하기 편하게, 시간 을 분 으로 통합하여 계산 했다.

Code

​x
public class Programmers_155651 {

    final int CLEAN_TIME = 10;
    final int MAX_TIME = 60 * 24 + CLEAN_TIME;

    public int solution(String[][] book_time) {
        int answer = 0;

        int[] timeCheck = new int[MAX_TIME];

        for(String[] time : book_time) {
            String start_time = time[0];
            String end_time = time[1];

            timeCheck[bookCheck(start_time)] += 1;
            timeCheck[bookCheck(end_time) + CLEAN_TIME] -= 1;
        }

        for(int i = 1; i < MAX_TIME; i++) {
            timeCheck[i] += timeCheck[i - 1];
            answer = Math.max(answer, timeCheck[i]);
        }

        return answer;
    }

    public int bookCheck(String time) {
        String[] times = time.split(":");
        int hour = Integer.parseInt(times[0]);
        int minute = Integer.parseInt(times[1]);

        return (hour * 60) + minute;
    }
}