백준 15686, 2589

알고리즘

원복의 기본꼴

go(int here){
	visited[there] = 1; // 방문처리
    go(there);
    visited[here] = 0; // 원상복구
}

원복이란?

상태값이 그 다음 경우의 수에 반영되지 않는 것

백준 15686번- 치킨 배달
https://www.acmicpc.net/problem/15686

사고의 흐름

1차 흐름
(1) 무식하게 풀 수 있지 않을까?
(2) Logic을 생각
(3) 시간 복잡도 계산해보니 가능
(4) 문제 풀기

2차 흐름
(1) 무식하게 풀 수 있지 않을까?
(2) Logic을 생각
(3) 시간 복잡도 계산해보니 불가능
(4) 다른 로직을 생각해서 문제 풀기

어떻게 해야 도시의 치킨 거리가 가장 작게 구할 수 있을까?

(1) 무식하게 풀어보기
치킨집 하나씩 돌면서 각 치킨집이 가지는 거리의 값을 구한뒤,
이 치킨집을 정렬을 해서 제일 작은 순서대로 폐업시키지 않은 갯수만큼 거리를 더해준다.

(2) Logic 생각
가정 : 전부다 치킨집일경우

• 2<=N<=50
  (N,N)모두 순회 : 50 * 50 = 2500

탐색 알고리즘 사용(BFS,DFS)
가정 : 치킨집 하나에 전부 집인 경우
집의 갯수 : 최대 100개(2N)
치킨의 갯수 : 최대 13개

Combination(13,?) * 100(집순회)

Combination(13,?)가 가지는 가장 큰 값은 무엇일까?

• Combination(13,6) = 1716
• Combination(13,7) = Combination(13,6) = 1716

Combination은 중앙으로 갈 수록 가장 큰 값이 된다.
nCr = nCn-r
공식 : n! / r!(n-r)!

총 시간 복잡도
O(N) : 171600

순열 or 조합 + 로직 : 1억미만인 경우 진행해!

오케이! 충분히 풀 수 있겠구나
그럼 무식하게 풀어보자

Code

public class Main {

    public static int n,m;
    public static int[][] map;
    public static int ans;
    public static ArrayList<Node> chickenList;
    public static ArrayList<Node> houseList;
    public static boolean[] chickenVisited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

        map = new int[n][n];
        chickenList = new ArrayList<>();
        houseList = new ArrayList<>();

        // 치킨 리스트, 집 리스트 따로 저장
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if(map[i][j] == 1){
                    houseList.add(new Node(j,i));
                }else if(map[i][j] == 2){
                    chickenList.add(new Node(j,i));
                }
            }
        }

        ans = Integer.MAX_VALUE;
        chickenVisited = new boolean[chickenList.size()];
        go(0,0);

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void go(int start, int cnt){
        if(cnt == m){ // 방문하고자 하는 치킨집을 다 선택한 경우
            int tot = 0;

            for (int i = 0; i < houseList.size(); i++) { // 각 집을 돌아다니면서
                int tmp = Integer.MAX_VALUE;
                for (int j = 0; j < chickenList.size(); j++) {
                    if(chickenVisited[j]){ // 선택받은 치킨 집인경우
                        int dis = Math.abs(houseList.get(i).x - chickenList.get(j).x) + Math.abs(houseList.get(i).y - chickenList.get(j).y);
                        tmp = Math.min(tmp,dis); // 집과 치킨집의 최소 거리 찾기
                    }
                }
                tot += tmp; // 각 집의 거리 더하기
            }
            ans = Math.min(ans,tot); // 모든 집의 거리를 더한 값 중에 최솟값을 정답 추출
            return;
        }

        // 백 트래킹
        for (int i = start; i < chickenList.size(); i++) {
            chickenVisited[i] = true; // 방문할 치킨집을 true로!
            go(i+1, cnt+1); // 재귀를 통해서 또 방문하고자 할 치킨집 찾기
            chickenVisited[i] = false; // 방문했던 집 false로 변경하기
        }
    }

    public static class Node { // x,y좌표를 표현하기 위한 class
        int x;
        int y;

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

백준 - 2589번 보물섬

흐름

(1) 두 땅사이간의 최단거리 중에 가장 큰 값을 호출한다

무식하게!
N,M : 최대 50
보물의 갯수 : 2개
Combination(50,2) = 1225
전부다 육지인 경우 : 50 x 50 = 2500

총 시간 복잡도
O(N) : 1225 x 2500 = 3062500

1억미만이네? 진행해!

1. Combination(n,2) x bfs(n,m)을 한번에
2. (nxm)xbfs(n,m)으로 해도 똑같다!

기준점을 하나로 잡고 모든 땅의 거리를 측정해서 가장 값이 큰 것을 찾으나, 조합을 이용해 두 지점을 선택해서 땅의 거리를 측정해서 가장 값이 큰 것을 찾으나 같은 방식이다!

Code

public class Main {
    static int n;
    static int m;
    static String[][] map;
    static int[][] visited;

    static int[] dx;
    static int[] dy;

    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

        map = new String[n][m];
        visited = new int[n][m]; // 0으로 자동 초기화됨
        dx = new int[]{0,1,0,-1};
        dy = new int[]{-1,0,1,0};
        ans = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            map[i] = br.readLine().split("");
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j].equals("L")){ // 육지를 찾은 경우
                    ans = Math.max(bfs(i,j),ans); // 제일 멀리 떨어진 경우를 찾아야 함
                }
            }
        }

        bw.write(ans+"\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static int bfs(int y, int x){ // stack 사용

        for (int i = 0; i < visited.length; i++) { // 방문 초기화
            Arrays.fill(visited[i],0);
        }

        visited[y][x] = 1; // 첫 방문 visited[y][x] = 1 로 초기화
        // 재방문 하지 않기 위해서

        int maxValue = Integer.MIN_VALUE;

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x,y));

        while(queue.size() > 0){

            Node node = queue.poll(); // 가져오기

            x = node.x;
            y = node.y;

            maxValue = Math.max(visited[y][x],maxValue);

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if(map[ny][nx].equals("L") && visited[ny][nx] == 0){
                    visited[ny][nx] = visited[y][x] + 1;
                    queue.add(new Node(nx,ny));
                }
            }
        }

        // 각 지점의 최댓값 찾기
        return maxValue - 1; // 거리이므로 자기 자신 제거
    }

    static class Node{
        int x;
        int y;

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

백준 16234 - 인구이동

흐름

(1) 인구 이동이 진행되지 않을때 까지 반복 = 최대 2000
(2) 모든 칸 탐색 BFS(N,N) = 2500

O(N) : 2000 x 2500 = 5000000 (오백만)
1억 미만이므로 진행해!

package 큰돌의터전알고리즘강의.three주차.인구이동;

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

public class Main {
    static int N;
    static int L;
    static int R;
    static int[][] map;
    static int[][] visited;

    static int[] dx;
    static int[] dy;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        N = Integer.parseInt(stk.nextToken());
        L = Integer.parseInt(stk.nextToken());
        R = Integer.parseInt(stk.nextToken());

        map = new int[N][N];
        visited = new int[N][N];

        dx = new int[]{0,1,0,-1};
        dy = new int[]{-1,0,1,0};

        for (int i = 0; i < N; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }

        // 국경 찾기 - visited로 열린 국경 찾기
        // 열린 국경 : 2 | 닫힌 국경 : 1
        // 열린 국경끼리 점수 초기화 -> 다시 국경 찾기
        // 열린 국경이 없을때 까지 반복

        int result = 0;

        while(true){

            if(move() == 0){ // 열린 국경이 없을때까지
                break;
            }else{
                result++;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static int move(){ // 움직여라!
        int count = 0;

        // 고립될 수 도 있다.
        for (int y = 0; y < N; y++) { // y
            for (int x = 0; x < N; x++) { // x
                if(visited[y][x] == 0){ // 방문하지 않은 경우
                    Queue<Node> queue = new LinkedList();
                    ArrayList<Node> list = new ArrayList<>();

                    Node node = new Node(x,y);
                    queue.add(node); // 큐에 노드 넣어주기
                    list.add(node); // 값들 넣어주기

                    int sum = map[node.y][node.x];
                    visited[node.y][node.x] = 1;

                    // bfs
                    while(queue.size() > 0){
                        Node cur = queue.poll();

                        for (int k = 0; k < 4; k++) {
                            int nx = cur.x + dx[k];
                            int ny = cur.y + dy[k];
                            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                            if(visited[ny][nx] == 0){
                                int gap = Math.abs(map[ny][nx] - map[cur.y][cur.x]);
                                if(gap >= L && gap <= R){
                                    queue.add(new Node(nx,ny)); // queue에 넣고
                                    list.add(new Node(nx,ny));
                                    visited[ny][nx] = 1;
                                    count++; // 갯수 플플
                                    sum += map[ny][nx];
                                }
                            }
                        }
                    }

                    if(count > 0){

                        int average = sum / list.size(); // 평균 값 구하기

                        for (int k = 0; k < list.size(); k++) {
                            Node cur = list.get(k);
                            map[cur.y][cur.x] = average; // map 값 조정하기
                        }
                    }
                }
            }
        }

        for (int i = 0; i < visited.length; i++) { // visited 배열 초기화
            Arrays.fill(visited[i],0);
        }

        return count;
    }

    public static class Node{
        int x;
        int y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}