- 문제: https://www.acmicpc.net/problem/4179
- 분류: BFS
- 난이도: G4
- 소요시간: 20m
- 자아성찰:
- BFS 사용 접근법은 맞았으나 방문처리를 깜빡해서 79%에서 계속 실패하고 시간이 오래 걸렸다.
- 접근법 : 불 위치를 큐에 우선으로 넣어 이동 및 방문처리 -> 지훈이 위치 이동 및 방문처리
- 최초 지훈이 위치(J) 및 불들의 위치(F)에 대해서도 방문처리를 해주었어야 하는데 이걸 놓쳐서 한참 헤맸다.
- BFS 문제는 구현 자체는 까다롭지 않으나, 문제 조건에 따른 방문처리, 추가적인 플래그 작업 등에 신경쓰도록 하자.!
- BFS 사용 접근법은 맞았으나 방문처리를 깜빡해서 79%에서 계속 실패하고 시간이 오래 걸렸다.
4179번: 불!
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자
www.acmicpc.net
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 B_4179 {
public static int result = -1;
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, 1, 0, -1};
public static boolean[][] map;
public static int R, C;
public static Node J;
public static Queue<Node> queue = new LinkedList<>();
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());
map = new boolean[R + 1][C + 1];
// map을 벗어난 첫번째 열/행 방문처리
for (int i = 0; i <= R; i++) {
map[i][0] = true;
}
for (int i = 0; i <= C; i++) {
map[0][i] = true;
}
for (int i = 1; i <= R; i++) {
String s = br.readLine();
for (int j = 1; j <= C; j++) {
char ch = s.charAt(j - 1);
// 벽은 이동 불가
if (ch == '#') {
map[i][j] = true;
}
// 지훈이 위치
if (ch == 'J') {
// 이미 미로의 끝이라면 한번만 이동하면 탈출
if (i == 1 || j == 1 || i == R || j == C) {
System.out.println(1);
return;
}
J = new Node(i, j, 0);
map[i][j] = true;
}
// 불인경우 먼저 이동하므로 큐에 넣음
if (ch == 'F') {
queue.add(new Node(i, j, -1));
map[i][j] = true;
}
}
}
bfs();
System.out.println(result == -1 ? "IMPOSSIBLE" : result);
}
public static void bfs() {
queue.add(J);
while (!queue.isEmpty()) {
Node cur = queue.poll();
// 상하좌우 확인
for (int n = 0; n < 4; n++) {
int x = cur.i + dx[n];
int y = cur.j + dy[n];
// map을 넘어서는 경우 continue
if (x > R || y > C) continue;
// 방문하지 않은 위치인 경우
if (!map[x][y]) {
// 방문 처리
map[x][y] = true;
// 불이 아닌 경우
if (cur.c != -1) {
// 다음 위치 미로 끝 여부 확인
if (x == 1 || y == 1 || x == R || y == C) {
// 다음위치(+1) / 다음위치에서 한번 더 이동 (+1)
result = cur.c + 2;
return;
} else {
// 현재 위치 이동횟수 + 1 큐에 삽입
queue.add(new Node(x, y, cur.c + 1));
}
} else {
// 불인 경우 큐에 바로 삽입
queue.add(new Node(x, y, -1));
}
}
}
}
}
public static class Node {
int i;
int j;
int c;
public Node(int i, int j, int c) {
this.i = i;
this.j = j;
this.c = c;
}
}
}
'Algorithm' 카테고리의 다른 글
백준[15787] - 기차가 어둠을 헤치고 은하수를 (0) | 2024.03.26 |
---|---|
백준[17352] - 여러분의 다리가 되어 드리겠습니다! (0) | 2024.03.14 |
백준[15927] - 회문은 회문아니야!! (1) | 2024.03.05 |
백준[11060] - 점프 점프 (0) | 2024.03.04 |
백준[2776] - 암기왕 (0) | 2024.02.19 |