백준 - 내리막길 1520, 겹치는 선분 1689

백준 문제 중 내리막길과 겹치는 선분 문제에 대한 풀이가 작성되어 있습니다. 원래 파이썬으로만 풀었는데, 최근에 오토에버 코테를 노리면서 자바로 언어를 급 변경했다. 사실 나에게 언어는 큰 장벽이 아니기 때문에 탐색 알고리즘을 구현하는 것에는 딱히 어려움이 없는 것 같다.

 

백준 - 내리막길 1520, 겹치는 선분 1689

 

코딩 테스트 연습 문제 풀이

 

1. 내리막길

2. 내리막길 코드

3. 겹치는 선분

4. 겹치는 선분 코드

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

내리막길

• 처음에 찐 DFS로 풀이를 했다가 시간초과를 맞았다.
• 아이디어는 떠올렸는데, 구현을 못하겠어서 다른 사람의 풀이를 참고했다가 하나의 알고리즘을 알아가게 되었다.
• 이것은 일종의 DFS + DP를 조합한 것이다.
• 특정 칸에서 목적지까지의 경로 수를 알고 있으면 쉽게 풀 수 있지 않을까? 라는 아이디어에서 시작된 풀이라고 이해하면 쉽다.
• 현재 위치에서 갈 수 있는 다음 칸(n_node)이 이미 방문했던 노드라면, 굳이 그 칸 이후를 탐색할 필요가 없다.
• 또한, n_node에서 목적지까지 가는 것이 가능하다면, 현재 위치에서 목적지까지 가는 것 역시 가능하다.
• 예를 들면, 아래의 그림과 같이 설명할 수 있다.

• (3, 3)에서 목적지까지 가는 1개의 경로를 가지고 있고, (2, 4)에서도 목적지까지 가는 1개의 경로를 가지고 있다면, (3, 3)과 (2, 4)를 갈 수 있는 현재 위치인 (2, 3)은 목적지까지 가는 경로 2개를 가지고 있는 것과 같다.
• 이를 위해 방문하지 않은 노드는 -1로 두고, 방문한 순간부터 내가 갈 수 있는 다음 칸에서 목적지까지의 경로가 몇 개인지 살피는 것이 코드의 핵심이다.

내리막길 코드

import java.util.*;
import java.io.*;
public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int answer = 0;
    static boolean isInTheMap(int x, int y, int limitX, int limitY) {
        if (x > -1 && x < limitX && y > -1 && y < limitY)
            return true;
        return false;
    }
    static int dfs(int x, int y, int[][] maps, int[][] visited) {
        if (x == maps.length - 1 && y == maps[0].length - 1) {
            return 1;
        } else if (visited[x][y] != -1) {
            return visited[x][y];
        }else {
            visited[x][y] = 0;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (isInTheMap(nx, ny, maps.length, maps[0].length) && maps[x][y] > maps[nx][ny]) {
                    visited[x][y] = visited[x][y] + dfs(nx, ny, maps, visited);
                }
            }
        }
        return visited[x][y];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int[][] maps = new int[M][N];
        int[][] visited = new int[M][N];
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++) {
                maps[i][j] = sc.nextInt();
                visited[i][j] = -1;
            }
        answer = dfs(0, 0, maps, visited);
        System.out.println(answer);
    }
}

겹치는 선분

• 겹치는 선분의 아이디어는 더 간단하다.
• 처음에는 끝나는 점을 기준으로 정렬한 다음 세보려고 했는데, 도저히 구현할 수가 없었다.
• 따라서 모든 좌표 칸에 선분이 있으면 +1씩 더하면서 기록을 하고 싶었는데, 시간 복잡도 때문에 할 수가 없었다.
• 그래서 조금 찾아본 결과 정말 간단한 아이디어를 찾을 수 있었다.
• 선분이 시작될 때 +1, 끝날 때 -1을 하면서 현재 겹쳐 있는 선분 수를 카운팅할 수가 있었다.
• 이때, 주의할 점은 선분이 끝나는 점과 다른 선분의 시작점이 동일한 경우 겹치지 않는 것으로 처리해야 하기 때문에 정렬 기준을 끝점이 먼저 오도록 해야 한다.
  • 기본적으로는 점의 위치를 기준으로 오름차순 정렬한다.
• 이것을 위해서 한 선분의 시작지점과 끝점을 같이 유지할 필요가 없다.
  • 실제로 코드 상에서 배열에 넣을 때, 서로 다른 행에 삽입된다.
  • 이것은 서로를 알지 못한다는 것을 의미한다.

겹치는 선분 코드

import java.util.*;
import java.io.*;
public class Main {

    public static void main(String[] args) throws IOException {
//        Scanner sc = new Scanner(System.in);
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[][] edges = new int[N*2][2];
        for (int i = 0; i < N*2; i++) {
            String[] s = bf.readLine().split(" ");
            edges[i][0] = Integer.parseInt(s[0]);
            edges[i][1] = 1;
            edges[i+1][0] = Integer.parseInt(s[1]);
            edges[i+1][1] = -1;
            i++;
        }

        Arrays.sort(edges, ((o1, o2) -> {
            return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
        }));

        //Arrays.stream(edges).forEach(item -> {System.out.println(item[0] + " " + item[1]);});
        int count = 0;
        int maxCount = 0;
        for (int i = 0; i < edges.length; i++) {
            count += edges[i][1];
            maxCount = Math.max(count, maxCount);
        }
        System.out.println(maxCount);
    }
}