728x90
반응형
https://www.acmicpc.net/problem/3055
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static class Node { int x; int y; int type; Node(int x, int y, int type) { this.x = x; this.y = y; this.type = type; } } static int R, C; static char[][] map; static boolean[][] visited; static Queue<Node> q = new LinkedList<>(); static int[] dxy = { 1, 0, -1, 0, 1 }; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); R = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken()); int startX = 0, startY = 0; map = new char[R][C]; visited = new boolean[R][C]; for (int i = 0; i < R; i++) { String line = br.readLine(); for (int j = 0; j < C; j++) { map[i][j] = line.charAt(j); if (map[i][j] == '*') { q.offer(new Node(i, j, 1)); visited[i][j] = true; } if (map[i][j] == 'S') { startX = i; startY = j; } } } System.out.println(bfs(startX, startY)); } static String bfs(int row, int col) { int[][] dist = new int[R][C]; q.offer(new Node(row, col, 0)); visited[row][col] = true; while (!q.isEmpty()) { Node cur = q.poll(); if (cur.type == 0 && map[cur.x][cur.y] == 'D') { return String.valueOf(dist[cur.x][cur.y]); } for (int i = 0; i < 4; i++) { int nx = cur.x + dxy[i]; int ny = cur.y + dxy[i + 1]; if (nx < 0 | nx >= R | ny < 0 | ny >= C) continue; // 두더지 if (cur.type == 0) { if (!visited[nx][ny] && map[nx][ny] == '.' || map[nx][ny] == 'D') { visited[nx][ny] = true; q.offer(new Node(nx, ny, 0)); dist[nx][ny] = dist[cur.x][cur.y] + 1; } } // 물 if (cur.type == 1) { if (!visited[nx][ny] && map[nx][ny] == '.' || map[nx][ny] == 'S') { visited[nx][ny] = true; q.offer(new Node(nx, ny, 1)); } } } } return "KAKTUS"; } } | cs |
728x90
'Algorithm > BOJ' 카테고리의 다른 글
백준) 2812_크게 만들기 (0) | 2023.06.07 |
---|---|
백준) 1449_수리공 항승 (0) | 2023.05.18 |
백준) 7569_토마토2 (2) | 2023.05.17 |
백준) 7576_토마토 (1) | 2023.05.17 |
백준) 2133_타일 채우기 (0) | 2023.05.16 |