알고리즘/백준
[Java] 1103 게임 - BFS, DP
Garonguri
2022. 2. 6. 01:37
728x90
https://www.acmicpc.net/problem/1103
1103번: 게임
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는
www.acmicpc.net
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class bj1103 {
static int N, M;
static int result;
static boolean checking;
static int[][] cnt;
static char[][] board;
static int[][] del = {{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String[] args) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new char[N][M];
cnt = new int[N][M];
//보드 입력 받는 부분.
for(int i=0;i<N;i++){
String tmp = br.readLine();
for(int j=0;j<M;j++){
board[i][j] = tmp.charAt(j);
}
}
//BFS돌림. 보드의 가장 왼쪽 위부터.
result =BFS(0,0);
if(checking){
System.out.println(-1);
}else{
System.out.println(result);
}
}
public static int BFS(int x, int y){
LinkedList<xy> queue = new LinkedList<>();
queue.offer(new xy(x, y)); //x,y를 큐에 삽입
int count=0;
while(!queue.isEmpty()){
int size = queue.size();
count+=1;
for(int i=0;i<size;i++){
//size를 구해주지 않고 여기로 바로 넣었더니 바로바로 안정해져서 틀림.
int c_x = queue.peek().x; //queue에서 x,y 저장.
int c_y = queue.peek().y;
queue.poll(); //queue에서 제거
for (int d = 0; d < 4; d++) {
int n_x = c_x + ((board[c_x][c_y] - '0') * del[d][0]);
int n_y = c_y + ((board[c_x][c_y] - '0') * del[d][1]);
if (isIn(n_x, n_y) && cnt[n_x][n_y] < count) { //카운트를 세야됨.
// System.out.println("n_x : " + n_x + ", n_y : " + n_y + ", cnt[nx][ny] : " + cnt[n_x][n_y] + ", count : " + count);
cnt[n_x][n_y] = count;
queue.offer(new xy(n_x, n_y));
}
}
}
if(count >N*M){
checking = true;
break;
}
}
return count;
}
static boolean isIn(int r, int c){
return 0<=r && 0<=c && r<N && c<M && board[r][c] != 'H';
}
public static class xy{
int x, y ;//좌표를 저장
xy(int x, int y){
this.x = x;
this.y = y;
}
}
}
|
cs |
[풀이]
BFS와 DP를 이용해서 푼 문제이다.
2022.01.30 - [Algorithm/백준] - [Java] 7569 토마토 - BFS
[Java] 7569 토마토 - BFS
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수
garonguri.tistory.com
토마토라는 문제와 유사하다. 많은 부분을 참고하여 풀었다 ^.^
다른 부분이 있다면 while문 안에서 queue의 size만큼만 pop을 시키는 부분이었는데 이를 통해 쓸데 없는 이동을 줄일 수 있었다.
728x90