boj)2178 - 미로 탐색
2020. 9. 3. 18:20ㆍPS/boj
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];
'PS > boj' 카테고리의 다른 글
boj)2644 - 촌수계산 (0) | 2020.09.05 |
---|---|
boj)7576 - 토마토 (0) | 2020.09.05 |
boj)1012 - 유기농 배추 (0) | 2020.09.03 |
boj)2667 - 단지번호붙이기 (0) | 2020.09.03 |
boj)2606 - 바이러스 (0) | 2020.09.03 |