kingsubin

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Node {
    int index;
    int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public int getIndex() {
        return index;
    }

    public int getDistance() {
        return distance;
    }
}

public class Main {

    static int n, m, nx, ny;
    static int[][] graph = new int[101][101];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Node node;

    public static int bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));

        while (!q.isEmpty()) {
            node = q.poll();
            x = node.getIndex();
            y = node.getDistance();

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

                if (nx < 1 || nx > n || ny < 1 || ny > m) {
                    continue;
                }

                if (graph[nx][ny] == 0) {
                    continue;
                }

                if (graph[nx][ny] == 1) {
                    graph[nx][ny] = graph[x][y] + 1;
                    q.offer(new Node(nx, ny));
                }
            }
        }

        return graph[n][m];
    }

    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 st = new StringTokenizer(br.readLine());

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

        // 그래프 입력
        for (int i = 1; i <= n; i++) {
            String str = br.readLine();
            for (int j = 1; j <= m; j++) {
                graph[i][j] = (str.charAt(j-1) - '0');
            }
        }

        bw.write(bfs(1, 1) + "\n");
        bw.flush();
        bw.close();
    }
}

 

- 혼자 생각이 잘 안났음 ..

- 이전에 봤던 미로찾기 풀이 참조함

- 봤던건데도 다시 풀려니까 안되넴 ...

 

 

1. graph 에서 1로표시된 부분만 이동하면서 목적지까지 이동했을때 이동 카운트를 구해야한다.

2. bfs로 접근 -> Queue 자료구조 사용 

3. 일단 노드가 서로 연결됬다고 보는게 아니라 좌표가 계속 움직여야 하니까 상하좌우를 생각

 

4. Queue 안에 Node 클래스를 넣어서 사용, 왜냐면 x, y 좌표가 필요하다

5. Queue가 빌때까지 while roof

5-1) Queue 에서 Node를 꺼내고 그 Node에 있는 x, y값을 이용해서 상하좌우 4번 움직인다.

5-2) nx, ny를 기준으로 graph를 벗어나면 roof 종료

5-3) graph[nx][ny] 값이 또한 0이면 움직일 수 없으므로 roof 종료

5-4) graph[nx][ny] == 1일때만 움직일 수 있다.

5-5) graph[nx][ny] 값에 현재값 + 1을 해주면 한 칸 이동할때마다 값이 계속 1씩 증가하게 된다.

       -> 배열 자체에 이동거리를 넣는거라고 생각

5-6) Queue에 Node(nx, ny)를 넣는다

6. 정답 출력 graph[n][m]; 

 

 

---

www.acmicpc.net/problem/2178