리모콘 [백준#1107]

골드5

문제

• 타겟 채널 N이 주어진다 (0 <= N <= 500000)
• 선택지는 0~9 숫자 또는 + (채널 + 1), - (채널 - 1)
• M개의 고장난 채널이 주어진다
• 시작 채널은 100이다.

최소 이동으로 N으로 이동해라

풀이

ans 변수를 가장 단순한, 100부터 하나씩 올라/내려가는 이동 수로 초기화한 다음 최적화한다.

int ans = Math.abs(N - 100);

이제 0부터 넉넉잡아 999999까지 for loop을 돌면서 더 나은 답안을 찾고자 한다.

for (int i = 0; i <= 999999; i++) {
	...
}

i의 각 자릿수마다 고장난 버튼인지 확인한다.

• 고장난 버튼이면 성립 불가한 경우의 수기 때문에 넘어간다.
• 고장난 버튼 없이 마지막 자릿수까지 도달하면 현재 i에서 N까지 도달하는데 필요한 1단위 이동 수와 i를 입력하는데 필요한 이동 수 (values.length)를 기존 ans값과 비교하여 최솟값을 저장한다.

int ans = Math.abs(N - 100);
for (int i = 0; i <= 999999; i++) {
    char[] values = String.valueOf(i).toCharArray();
    for (int j = 0; j < values.length; j++) {
        if (broken[values[j] - '0']) {
            break;
        } else if (j == values.length - 1) {
            ans = Math.min(ans, Math.abs(i - N) + values.length);
        }
    }
} 
System.out.println(ans);

오답

고장난 버튼의 수가 0인 경우 숫자가 아예 주어지지 않는다. 이를 고려하여 if문을 이용하여 버퍼드리더를 사용했어야 한다. 이 때문에 NullPoint 에러가 발생했다.

---

경로 찾기 [백준#11403]

실버1

문제

• 가중치 없는 방향 그래프 G
• 모든 정점 (i, j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지
• 그래프의 인접 행렬이 1, 0 값을 담아 주어진다
• i번째 줄의 i번째 숫자는 항상 0이다

풀이

각 정점 i에 대해서 dfs를 수행해서 j로 이어진다면 그 결과값을 result[i][j] = 1로 저장한다.

for (int i = 0; i < N; i++) {
    visited = new boolean[N];
    dfs(i, i);
}

dfs는 다음과 같이 수행한다

private static void dfs(int start, int target) {
    for (int next = 0; next < N; next++) {
        if (matrix[target][next] == 1 && !visited[next]) {
            visited[next] = true;
            result[start][next] = 1;
            dfs(start, next);
        }
    }
}

---

탈출 [백준#3055]

골드4

문제

• 2D 지도가 주어진다
  • 비어있는 곳, 물, 돌, 비버의 굴, 고슴도치
• 고슴도치는 매 분 인접 4칸 중 하나로 이동
  • 물이 찰 예정인 곳으로 이동 불가
• 물은 4분면 인접 칸으로 확장
• 고슴도치가 비버의 굴에 도달하는 최단거리를 출력하라
  • 불가하면 'KAKTUS'

풀이

1. 입력 값을 받는다

(1) 물 칸은 큐에 모은다
(2) 고슴도치의 위치를 확인한다

grid = new char[R][C];
waterGrid = new int[R][C];
ArrayDeque<int[]> waterQueue = new ArrayDeque<>();
int startY = -1, startX = -1;

for (int i = 0; i < R; i++) {
    String line = br.readLine();
    for (int j = 0; j < C; j++) {
        grid[i][j] = line.charAt(j);
        if (isWater(i, j)) waterQueue.addLast(new int[] {i, j});
        else waterGrid[i][j] = Integer.MAX_VALUE;
        if (isHedgeHog(i, j)) {
            startY = i;
            startX = j;
        }
    }
}

2. 물 확장에 관한 그리드를 저장한다

1초마다 인접 4분면으로 확장한다.

private static void updateWater(ArrayDeque<int[]> queue) {

    while (!queue.isEmpty()) {
        int[] node = queue.pollFirst();
        int y = node[0];
        int x = node[1];

        for (int d = 0; d < 4; d++) {
            int ny = y + DY[d];
            int nx = x + DX[d];

            if (!isValidCoordinate(ny, nx) || waterGrid[ny][nx] != Integer.MAX_VALUE || isRock(ny, nx) || isBeaver(ny, nx)) continue;

            waterGrid[ny][nx] = waterGrid[y][x] + 1;
            queue.addLast(new int[] {ny, nx});
        }
    }
}

3. 물 그리드와 문제의 요구사항을 반영하여 고슴도치의 이동을 구현한다

private static int bfs(int startY, int startX) {
    ArrayDeque<int[]> queue = new ArrayDeque<>();
    int[][] visited = new int[R][C];

    queue.addLast(new int[] {startY, startX});
    visited[startY][startX] = 1;

    while (!queue.isEmpty()) {
        int[] node = queue.pollFirst();
        int y = node[0];
        int x = node[1];

        if (isBeaver(y, x)) return visited[y][x] - 1;


        for (int d = 0; d < 4; d++) {
            int ny = y + DY[d];
            int nx = x + DX[d];

            if (!isValidCoordinate(ny, nx) || visited[ny][nx] > 0 || isRock(ny, nx) || isWater(ny, nx)) continue;
            if (waterGrid[ny][nx] > visited[y][x] || waterGrid[ny][nx] == Integer.MAX_VALUE) {
                visited[ny][nx] = visited[y][x] + 1;
                queue.addLast(new int[] {ny, nx});
            }

        }
    }
    return -1;
}

---