[자바] 백준 27453 - 귀엽기만 한 게 아닌 한별 양 (java)

 문제 : boj27453

---

 

필요 알고리즘 개념

• 너비 우선 탐색 (bfs)
  
  • BFS긴 한데 상당히 난이도가 높은 BFS인 것 같다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  BFS 추천 문제이다. 문제가 좋은 것 같다.

 

  BFS에 대해 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고해보자. 특히 '방문체크에 대해 좀 더 써봄' 부분이 필요하다.

 

  BFS로 풀려면 모든 경우의 수를 파악해 방문체크를 해줘야 한다. 이 문제에서는 '해당 마을에 어느방향에서 들어왔는지'가 된다. 아래 방문체크 배열 v에서 [r][c][4]는 (r,c) 위치에 4방향 중 어떤 방향으로 들어왔는지 방문체크하는 것에 해당한다.

boolean[][][] v = new boolean[r][c][4];

 

  사실 처음엔 아래 이미지처럼 연속된 3칸씩 들어올 때, 중앙부분에 둘다 좌측에서 들어오지만, 위에서 돌아왔는지 아래서 돌아왔는지에 따라 방문체크가 달라질거라 생각해서, 이전보다 더 합이 작은 상태로만 들어올 수 있게 했었다.

if (sum > k || v[nr][nc][nd] <= sum) continue;

 

  풀고난 후 'pill27211'님의 코드를 보고 어차피 저기서 한칸 더 가면 아래처럼 3칸을 봐야하는 셈이라, 거리까진 필요없고 들어온 방향까지만 확인하면 된다는걸 깨달았다. 이걸로 -280ms !

 

  방문체크가 해결됬다면 이제 BFS를 진행하면 되는데, 이 문제의 경우엔 진행 시 이전 지점에 대한 정보도 함께 필요하다. (최근 3개 이하 칸의 불상사의 개수 합을 알 수 있어야 하므로)

  그렇다면 현재 지점에 대해, 이전 지점의 위치정보를 기억하고 있거나 혹은 이전에 어느방향에서 들어왔는지 알고 있어야 한다. 내 경우엔 이전 방향으로 되돌아가지 않도록 처리도 같이 하려고 후자를 선택했다(이전 위치정보가 있어도 이건 처리가능하긴 하다.).

for (int d = 0; d < 4; d++) {
    if (cur.dir == d) continue;
	...
    int nd = 3-d;
    ...
}

  

  내 경우 이동할 위치를 나타내는 배열을 다음과 같이 써뒀다. 따라서 3-d를 통해 역방향(상 <-> 하, 좌 <-> 우)을 표현할 수 있도록 엇갈려서 작성해두었다.

private static final int[] DR = {-1, 0, 0, 1};
private static final int[] DC = {0, -1, 1, 0};

 

  로직은 다음처럼 진행된다.

1. 'S' 지점을 큐에 넣는다.

2. 큐에서 하나를 뺀게 'H' 위치라면 집에 도착한거니 거리를 출력하고 끝낸다.

3. 4방향을 보면서 다음 위치를 살펴본다(d++).

4. 현재 위치(cur)와, 이전 위치(cur과 cur.dir을 통해 알 수 있음), 다음 위치(nr, nc)를 가지고 연속된 3개 칸의 불상사 합을 구한다(sum).

5. 불상사합이 k 이상이면 못간다.

6. dist를 증가시켜주며 다음위치로 이동한다.

7. 최종적으로 'H'에 도달한 적이 없다면 -1을 출력한다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Node {
    int r, c, dir, dist;
    public Node(int r, int c) {
        this(r, c, -1, 0);
    }
    public Node(int r, int c, int dir, int dist) {
        this.r = r;
        this.c = c;
        this.dir = dir;
        this.dist = dist;
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int[] DR = {-1, 0, 0, 1};
    private static final int[] DC = {0, -1, 1, 0};

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        char[][] map = new char[r][c];
        Node start = null;
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = row.charAt(j);
                if (start == null && map[i][j] == 'S') {
                    start = new Node(i, j);
                }
            }
        }

        boolean[][][] v = new boolean[r][c][4];
        Queue<Node> q = new ArrayDeque<>();
        q.add(start);
        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (map[cur.r][cur.c] == 'H') {
                System.out.println(cur.dist);
                return;
            }
            for (int d = 0; d < 4; d++) {
                if (cur.dir == d) continue;
                int nr = cur.r + DR[d];
                int nc = cur.c + DC[d];
                if (nr<0||nr>=r||nc<0||nc>=c||map[nr][nc]=='X') continue;

                int nd = 3-d;
                int sum = sum(map, cur.r, cur.c, cur.dir, nr, nc);

                if (sum > k || v[nr][nc][nd]) continue;
                v[nr][nc][nd] = true;
                q.add(new Node(nr, nc, nd,cur.dist+1));
            }
        }
        System.out.println(-1);
    }

    private int sum(char[][] map, int r, int c, int dir, int nr, int nc) {
        int answer = bss(map, nr, nc);
        if (dir != -1) answer += bss(map, r+DR[dir], c+DC[dir]);
        return answer + bss(map, r, c);
    }

    private int bss(char[][] map, int r, int c) {
        return map[r][c]=='S'||map[r][c]=='H' ? 0 : map[r][c]-'0';
    }
}