https://www.acmicpc.net/problem/15686

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

 

[정답 코드]

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

public class Main {
    static int N, M;
    static int[][] graph;
    static ArrayList<int[]> house = new ArrayList<>();
    static ArrayList<int[]> chicken = new ArrayList<>();
    static ArrayList<int[]> selected = new ArrayList<>();
    static int result = Integer.MAX_VALUE;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 1) {
                    house.add(new int[]{i, j}); // 집의 좌표 저장
                } else if (graph[i][j] == 2) {
                    chicken.add(new int[]{i, j}); // 치킨집의 좌표 저장
                }
            }
        }
        visited = new boolean[chicken.size()];

        back(0, 0);
        System.out.println(result); // 출력
    }

    static void back(int depth, int start) {
        if (depth == M) { // M개를 뽑아서 selected 리스트에 M개 저장이 끝났다면
            int sum = 0;
            for (int[] h : house) { // 모든 집들과 치킨집과의 최소거리를 계산
                int min = Integer.MAX_VALUE;
                for (int[] s : selected) { // 선택한 M개의 치킨집과 집의 거리를 계산해 최소거리를 구함
                    int d = Math.abs(h[0] - s[0]) + Math.abs(h[1] - s[1]);
                    min = Math.min(d, min);
                }
                sum += min; // 그렇게 구한 최소거리를 sum에 저장
            }
            result = Math.min(result, sum); // 그렇게 구한 sum들중에 최소값만 저장
            return;
        }

        for (int i = start; i < chicken.size(); i++) { // 모든 치킨집들을 탐색함
            if (!visited[i]) {
                visited[i] = true;
                selected.add(chicken.get(i));
                back(depth + 1, i + 1);
                selected.remove(selected.size() - 1);
                // 탐색이 끝났다면 리스트를 비우기 위한 로직
                // 배열로 했다면 덮어씌울수 있지만 리스트라 제거해줘야함
                visited[i] = false;
            }
        }
    }
}

 

[설명]

백트래킹 알고리즘 : 

1. for문을 돌며 치킨집들중 M개의 치킨집을 골라 selected 리스트에 담는다.

2. selected 리스트에 M개의 치킨집이 저장 되었다면 집과 선택한 치킨집들과의 최소거리를 구한다.

3. 그렇게 구한 각집과 선택한치킨집과의 최소거리를 모두 더했다면

4. 다시 치킨집들 중 아까와 다른 M개의 치킨집을 골라 반복한다.

https://www.acmicpc.net/problem/14225

 

14225번: 부분수열의 합

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들

www.acmicpc.net

 

 

[정답 코드]

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

public class Main {
    static int[] arr, answer;
    static int N, max = 0;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());

        arr = new int[N];
        visited = new boolean[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max += arr[i];
        }
        answer = new int[max + 2]; // 최대 가능한 합 + 2 로 설정해야 메모리 낭비를 막을 수 있다

        dfs(0, 0);

        for (int i = 1; i < answer.length; i++) {
            if (answer[i] == 0) { // 0일 경우 해당 인덱스는 나온적 없는 숫자이므로 출력
                System.out.println(i);
                break;
            }
        }

    }

    static void dfs(int depth, int sum) {
        if (depth == N) { // depth 가 N일 경우 종료
            answer[sum] = 1; // 현재까지 저장된 sum 값은 이미 나온 숫자이므로 1로 변경
            return;
        }
        dfs(depth + 1, sum + arr[depth]); // 현재까지 저장된 sum + 현재 인덱스의 arr 값
        dfs(depth + 1, sum); // 현재 인덱스의 arr 값을 추가하지않고 다음 인덱스 탐색
    }
}

 

[설명]

배열의 원소를 입력받을 때마다 값을 max에 추가해 나올 수 있는 가장 큰 자연수를 계산한다. 나올 수 있는 자연수들이 담긴 배열 answer = new int[max+ 2] 해준다. 다른 코드에서는 문제에서 주어진 나올 수 있는 가장 큰 값으로 초기화 해주었지만 max가 적을수록 메모리낭비가 생기기 때문에 이처럼 해준다.

 

dfs로직 : 매개변수로 depth, sum을 받는다. depth는 현재의 인덱스 위치, sum은 현재까지 저장된 값이다. depth 가 N이 될 경우 초기에는 answer배열의 모든값이 0이기 때문에 answer[sum]을 임의의 값 1로 변경해준후 return 한다.

        dfs(depth + 1, sum + arr[depth]); // 현재까지 저장된 sum + 현재 인덱스의 arr 값
        dfs(depth + 1, sum); // 현재 인덱스의 arr 값을 추가하지않고 다음 인덱스 탐색

이 부분은 배열의 완전탐색을 하기위한 알고리즘이다. 인덱스를 증가시키면 배열을 탐색하다 현재 인덱스의 arr[depth] 더하고 다음 인덱스를 탐색할 경우에는 첫 번째를, 아니라면 두 번째를 실행해야한다. 모든 배열을 탐색해야하기 때문에 두 가지 모두 수행한다.

'코딩테스트' 카테고리의 다른 글

백준 1189번: 컴백홈[JAVA]  (0) 2024.03.28
백준 15686번: 치킨 배달[JAVA]  (0) 2024.03.28
백준 10819번: 차이를 최대로[JAVA]  (0) 2024.03.21
백준 1260번: DFS와 BFS[JAVA]  (0) 2024.03.20
백준 1068번: 트리[JAVA]  (1) 2024.03.15

https://www.acmicpc.net/problem/10819

 

10819번: 차이를 최대로

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

www.acmicpc.net

 

 

[정답 코드]

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

public class Main {
    static int result = Integer.MIN_VALUE;
    static int N;
    static int[] arr, selected;
    static boolean[] visited;

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

        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        visited = new boolean[N];
        selected = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0);

        System.out.println(result);
    }

    public static void dfs(int count) {
        if (count == N) {
            result = Math.max(result, getResult());
            return;
        }

        for (int i = 0; i < N; i++) { //
            if (!visited[i]) {
                visited[i] = true;
                selected[count] = arr[i];
                dfs(count + 1);
                visited[i] = false;
            }
        }
    }

    public static int getResult() {
        int sum = 0;
        for (int i = 0; i < N - 1; i++) {
            sum += Math.abs(selected[i] - selected[i + 1]);
        }
        return sum;
    }
}

 

[설명]

부르트 포스 알고리즘과 dfs를 활용해 풀었다. for문을 돌며 깊이 우선 탐색으로 count가 N이 될 때 까지 탐색하다 count 가 N이 될 경우 getResult() 메서드를 실행해 지금까지 저장했던 result 값과 비교해 최댓값을 출력한다. getResult() 메서드는 dfs 알고리즘을 돌며 count가 N이 될 때 까지 선택해왔던 숫자들을 담은 배열을 계산해주는 메서드이다.

'코딩테스트' 카테고리의 다른 글

백준 15686번: 치킨 배달[JAVA]  (0) 2024.03.28
백준 14225번: 부분수열의 합[JAVA]  (0) 2024.03.25
백준 1260번: DFS와 BFS[JAVA]  (0) 2024.03.20
백준 1068번: 트리[JAVA]  (1) 2024.03.15
백준 1991번: 트리 순회[JAVA]  (1) 2024.03.15

https://www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

 

[정답 코드]

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

public class Main {
    static int[][] graph;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); // 정점의 수
        int M = Integer.parseInt(st.nextToken()); // 간선의 수
        int V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점 번호

        graph = new int[N + 1][N + 1]; // 1부터 시작
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph[u][v] = graph[v][u] = 1; // 양방향 간선
        }

        visited = new boolean[N + 1];
        dfs(V);

        System.out.println();

        visited = new boolean[N + 1];
        bfs(V);
    }

    // dfs : 깊이우선탐색(재귀)
    public static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");

        if (v == graph.length) {
            return;
        }
        for (int i = 1; i < graph.length; i++) {
            if (graph[v][i] == 1 && visited[i] == false) {
                dfs(i);
            }
        }
    }

    // bfs : 너비우선탐색(큐)
    public static void bfs(int v) {
        Queue<Integer> q = new LinkedList<>();
        q.add(v);
        visited[v] = true;
        System.out.print(v + " ");

        while (!q.isEmpty()) {
            int tmp = q.poll();
            for (int i = 1; i < graph.length; i++) {
                if (graph[tmp][i] == 1 && visited[i] == false) {
                    q.add(i);
                    visited[i] = true;
                    System.out.print(i + " ");
                }
            }
        }
    }
}

 

[설명]

dfs 와 bfs의 기본문제이다. 항상 풀 때마다 개념정립이 애매했는데. 이 문제를 디버깅하면서 제대로 이해했다.

DFS는 재귀를 사용하고, BFS는 큐를 사용하는 방식을 사용했다.

 

 

https://www.acmicpc.net/problem/1068

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

 

 

[정답 코드]

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

public class Main {
    static int root;
    static Node[] tree;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        tree = new Node[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            tree[i] = new Node(parent); // 노드의 번호는 i, i번 노드의 부모는 parent 인 Node를 생성
            if (parent == -1) { // parent 번호가 -1 이면 해당 노드는 루트 노드
                root = i;
            }
        }

        // 루트 노드가 아닌 경우, 해당 노드의 부모 노드를 찾아 자식노드에 자신을 추가
        for (int i = 0; i < N; i++) {
            if (root != i) { // 루트노드가 아닐경우
                int parent = tree[i].parent; // i 번 노드의 부모노드를 꺼내서
                tree[parent].addChild(i); // 부모노드의 자식에 i번 노드를 추가해줌
            }
        }

        int removeNode = Integer.parseInt(br.readLine()); // 삭제 할 노드 번호
        if (removeNode == root) { // 루트 노드를 지울경우 전부 삭제되므로 0 출력
            System.out.println(0);
        } else {
            int parent = tree[removeNode].parent; // 삭제하려는 노드의 부모 노드의 값을 꺼냄
            tree[parent].removeChild(removeNode); // 그 부모노드의 자식노드들 중 삭제하려는 노드번호를 삭제
            int leafSize = getLeafSize(root); // 리프노드의 수를 카운팅
            System.out.println(leafSize);
        }
    }

    static int getLeafSize(int index) {
        if (tree[index].isLeaf()) { // 해당 노드의 자식노드가 없다면 true 를 반환해서
            return 1; // 1 반환
        }
        int sum = 0;
        for (int i = 0; i < tree[index].getChildrenSize(); i++) {
            sum += getLeafSize(tree[index].children.get(i)); // 반복문을 재귀적으로 돌며 자식노드가 없는 노드들을 탐색
        }
        return sum;
    }
}

// 노드 클래스
class Node {
    int parent; // 해당 노드의 부모 노드
    List<Integer> children; // 자식노드들

    public Node(int parent) {
        this.parent = parent;
        this.children = new ArrayList<>(); // 자식노드들은 ArrayList 로 생성
    }

    public void addChild(int child) { // 노드의 자식들을 ArrayList.add 로 삽입
        this.children.add(child);
    }

    public void removeChild(int child) { // 노드의 자식들을 ArrayList.remove 로 삭제
        this.children.remove(Integer.valueOf(child));
    }

    public boolean isLeaf() { // 노드의 자식이 없다면 true 반환
        return this.children.isEmpty();
    }

    public int getChildrenSize() { // 노드의 자식들의 개수를 ArrayList.size() 메서드를 활용해 출력
        return this.children.size();
    }
}

 

[설명]

저번에 풀었던 노드의 심화버전이다. 그래서 저번에 풀었던 코드를 조금만 수정해 풀려고 했으나 실패해 포기해 다른분들의 코드를 찾아보며 풀어버렸다.

예제 입력 1번을 예시로 설명을 해보자면

 

1. Node클래스 배열을 선언

  • 노드배열의 인덱스가 해당 노드의 밸류
    노드 클래스의 필드는 parent(부모노드번호), childrent(자식노드들을 ArrayList로 가변적으로 선언)
  • tree[0] = new Node(-1)
    tree[1] = new Node(0)
    tree[2] = new Node(0)
    tree[3] = new Node(1)
    tree[4] = new Node(1)
    root = 0

2. 각 클래스들의 부모를 찾아 자기자신을 그 부모노드의 자식으로 추가함

ArrayList.add 를 사용해 추가

  • i=0
    int parent = tree[0].parent = -1 // parent가  root 일 경우 if문 false

    i = 1
    int parent = tree[1].parent = 0
    tree[0].addChild(1);

    i = 2
    int parent = tree[2].parent = 0
    tree[0].addChild(2);

    i = 3
    int parent = tree[3].parent = 1
    tree[1].addChild(3);

    i = 4
    int parent = tree[4].parent = 1
    tree[1].addChild(4);

3. 삭제할 노드를 입력받아 해당 노드를 삭제함

  • 삭제할 노드를 입력받고 해당 노드의 부모노드를 탐색 -> 삭제하려는 부모노드의 자식들중 삭제하려는 노드와 같은 자식을 ArrayList.remove() 메서드로 삭제
  • removeNode = 2
    int parent = tree[2].parent = 0
    tree[0].removeChild(2)

4. 리프 노드를 카운팅

  • 루트노드부터 시작해 모든 자식노드들을 방문하며 어떤 노드의 Children.isEmpty가 true일경우 sum 을 1씩 증가시킴
  • 이 로직을 재귀적으로 반복해가며 모든 노드들을 방문함

 

'코딩테스트' 카테고리의 다른 글

백준 10819번: 차이를 최대로[JAVA]  (0) 2024.03.21
백준 1260번: DFS와 BFS[JAVA]  (0) 2024.03.20
백준 1991번: 트리 순회[JAVA]  (1) 2024.03.15
백준 16234번: 인구 이동[JAVA]  (1) 2024.03.13
백준 2493번: 탑[JAVA]  (0) 2024.03.12

https://www.acmicpc.net/problem/1991

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파

www.acmicpc.net

 

 

 

[정답 코드]

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

public class Main {
    static Node head = new Node('A', null, null); // 트리는 A부터 시작
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            char root = st.nextToken().charAt(0);
            char left = st.nextToken().charAt(0);
            char right = st.nextToken().charAt(0);

            insertNode(head, root, left, right);
        }

        preOrder(head);
        System.out.println();
        inOrder(head);
        System.out.println();
        postOrder(head);
        System.out.println();
    }


    static class Node {
        char value;
        Node left;
        Node right;

        Node(char value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static void insertNode(Node tmp, char root, char left, char right) {
        if (tmp.value == root) {
            tmp.left = (left == '.' ? null : new Node(left, null, null));
            tmp.right = (right == '.' ? null : new Node(right, null, null));
        } else {
            if (tmp.left != null) {
                insertNode(tmp.left, root, left, right);
            }
            if (tmp.right != null) {
                insertNode(tmp.right, root, left, right);
            }
        }
    }

    private static void preOrder(Node node) {
        if (node == null) { // 더 이상 값이 없을 때 까지
            return;
        }
        System.out.print(node.value); // 출력
        preOrder(node.left); // 왼쪽 노드 탐색
        preOrder(node.right); // 오른쪽 노드 탐색
    }

    private static void inOrder(Node node) {
        if (node == null) { // 더 이상 값이 없을 때 까지
            return;
        }
        inOrder(node.left); // 왼쪽 노드 탐색
        System.out.print(node.value); // 출력
        inOrder(node.right); // 오른쪽 노드 탐색
    }

    private static void postOrder(Node node) {
        if (node == null) { // 더 이상 값이 없을 때 까지
            return;
        }
        postOrder(node.left); // 왼쪽 노드 탐색
        postOrder(node.right); // 오른쪽 노드 탐색
        System.out.print(node.value); // 출력
    }
}

 

[설명]

트리를 순회하는 문제이다. 트리 탐색의 아주 기초문제이지만 너무 오랜만에 풀어서 도저히 풀 수가 없어 다른 글을 참고했다.

먼저 해결 방법은 다음과 같다.

 

1. Node 클래스를만든다.

  • Node 클래스는char value, Node left, Node right 구조를 가진 클래스이다.

2. Node 클래스에 insertNode메서드를 활용해 값을 입력한다.

  • insertNode는 (Node tmp, char root, char left, char right) 매개변수를 가지는데
    맨 처음 선언한 Node head 를 기준으로 null 이 아닌 노드를 계속 탐색한다.
    입력한 char root 값이 어떠한 Node의 value라면 그 노드의 왼쪽 노드와 오른쪽 노드에 
    값을 집어 넣는다.

3. 전위 순회 ,중위 순회 ,후위 순회 메서드를 각 각 사용해 출력한다.

  • 전위 순회 : 루트 -> 왼쪽  노드 -> 오른쪽 노드 순서
    중위 순회 : 왼쪽 노드 -> 루트 -> 오른쪽 노드 순서
    후위 순회 : 왼쪽 노드  -> 오른쪽 노드 -> 루트 순서

디버깅모드로 차근차근 이해해보면 금방 이해할 수 있다.

'코딩테스트' 카테고리의 다른 글

백준 1260번: DFS와 BFS[JAVA]  (0) 2024.03.20
백준 1068번: 트리[JAVA]  (1) 2024.03.15
백준 16234번: 인구 이동[JAVA]  (1) 2024.03.13
백준 2493번: 탑[JAVA]  (0) 2024.03.12
백준 7682번: 틱택토[JAVA]  (0) 2024.03.11

https://www.acmicpc.net/problem/16234

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

 

[정답 코드]

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

public class Main {
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1}; // 상하좌우순서
    static int N, L ,R;
    static ArrayList<int[]> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

        graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(move());
    }

    public static int move() { // 더이상 인구 이동이 일어나지 않을때 까지 반복
        int result = 0;
        while (true) {
            boolean isMove = false;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        int sum = dfs(i, j); // 방문하지 않은 곳 dfs 탐색
                        if (list.size() > 1) {
                            changePopulation(sum); // 국경이 열린 노드끼리 인구 이동
                            isMove = true;
                        }
                    }
                }
            }
            if (!isMove) {
                return result;
            }
            result++;
        }
    }

    public static void changePopulation(int sum) {
        int avg = sum / list.size();
        for (int i = 0; i < list.size(); i++) {
            int x = list.get(i)[0];
            int y = list.get(i)[1];
            graph[x][y] = avg;
        }
    }

    public static int dfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});

        list = new ArrayList<>();
        list.add(new int[]{x, y});

        visited[x][y] = true;
        int sum = graph[x][y];

        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            for (int i = 0; i < 4; i++) { // 4방탐색
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N) { // graph 범위 내
                    // 방문한적 없고, L과 R 사이일 때
                    if (!visited[nx][ny] && L <= Math.abs(graph[tmp[0]][tmp[1]] - graph[nx][ny]) && Math.abs(graph[tmp[0]][tmp[1]] - graph[nx][ny]) <= R) {
                        visited[nx][ny] = true; // 방문한곳으로 변경
                        queue.offer(new int[]{nx, ny}); // 새로 큐에 담아줌
                        list.add(new int[]{nx, ny}); // 연결된 나라끼리는 따로 좌표를 담아줌
                        sum += graph[nx][ny];
                    }
                }
            }
        }
        return sum;
    }
}

 

[설명]

dfs와 구현을 동시에 해야하는 문제이다. 

문제를 세분화해서 풀어야 한다.

1. 순회를하며 방문하지 않은 노드를방문한다. 모든 노드를방문할 때 까지 반복된다.
2. 방문한 노드에서 dfs 알고리즘을 구현. 

  • dfs 알고리즘 : 연결된 노드들의 좌표를 list에 담아줌. 연결된 노드들의 값을 모두 더함.

3. 연결된 것 노드의 체크가 끝나면 인구 이동을 시작.

  • 인구이동 로직 : 연결된 노드들의 좌표를 담았던 list를 하나씩 꺼내며 연결된 노드들의 값을 모드 더했던것을 적절히 나눠 값을 배분

4. 모든 노드들을 방문했다면 1일 증가

5. 1 ~ 5를 반복, 인구이동이 더이상 일어나지 않을 때 까지 반복

'코딩테스트' 카테고리의 다른 글

백준 1068번: 트리[JAVA]  (1) 2024.03.15
백준 1991번: 트리 순회[JAVA]  (1) 2024.03.15
백준 2493번: 탑[JAVA]  (0) 2024.03.12
백준 7682번: 틱택토[JAVA]  (0) 2024.03.11
백준 9372번: 상근이의 여행[JAVA]  (0) 2024.03.09

https://www.acmicpc.net/problem/2493

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        Stack<int[]> stack = new Stack<>();
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) { // 탑은 0번부터가 아닌 1번부터 시작
            int top = Integer.parseInt(st.nextToken()); // 현재 확인중인 탑
            while (!stack.isEmpty()) {
                if (stack.peek()[1] >= top) {
                    bw.write(stack.peek()[0] + " ");
                    break;
                }
                stack.pop();
            }
            if (stack.isEmpty()) {
                bw.write("0 ");
            }
            stack.push(new int[]{i, top});
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

[설명]

제일 왼쪽 탑부터 스택에 담긴 값들과 비교해가면 로직을 반복한다.

스택에는 높이가 작은 순서부터 큰순으로 오름차순으로값이 담기게 된다.

 

높은 6탑은 첫번째 탑이기 때문에 비교할 스택들이 없어 0을 bw.write 한 후 {탑의 위치, 탑의 높이}를 스택에 담는다.

 

높이 9탑은 스택에 담긴 6보다 높이가 높다. 그 뜻은 앞으로 확인할 탑들은 모두 높이 9 탑 때문에 스택에 담겼던 높이 6 탑을 만날 수 없다. 그러므로 높이 6 스택은 pop해준다. 높이 9 탑을 스택에 담는다.

 

높이 5탑과 스택에 담긴 높이9 탑과 비교해준다. 높이9 탑에 신호가 닿기 때문에 높이9의 위치를 출력해준 후 스택에 높이 5 스택을 담아준다.

 

높이 7탑과 스택에 담긴값과 비교해준다. 스택의 가장 위의 값인 높이 5와 비교를 해본다. 스택에 담겼던 스택 5탑은 현재 확인중인 높이 7탑 때문에 앞으로 모든신호를 못받게된다. 그러므로 스택에서 pop 해준다. 그 다음 스택에 담긴 값 높이 9랑 비교 하면 신호가 9에 닿는다. 9의 위치를 출력후 높이7 탑을 스택에 담는다.

 

높이 4탑과 스택에 담긴 값을 비교해본다. 스택의 top에 있는값 높이 7인탑과 비교해보니 바로 신호가 닿는다. 높이 7탑의 위치를 출력해준다.

+ Recent posts