16956번: 늑대와 양
크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게
www.acmicpc.net
문제 분류는 bfs로 되어있지만 bfs를 사용하지 않아도 해결 가능한 문제입니다.
저는 bfs방식으로 양의 위치를 큐에 담아서 하나씩 꺼내 확인하는 방법과
2중 for문을 이용해서 양의 위치에서 확인하는 방법으로 2가지로 해결해 보았습니다.
두 방법 모두 양의 위치에서 상, 하, 좌, 우 방향에 늑대가 있는지 확인합니다.
늑대가 있으면 0출력후 리턴, 없으면 놓을 수 있는 모든 방향에 울타리를 설치합니다.
문제가 스페셜저지이기 때문에 예제와 답이 다르게 나와도 늑대가 양이 있는 칸으로 갈수없다면 정답으로 할 수 있습니다. (물론 첫째줄에 출력하는 0과 1은 맞아야합니다.)
[bfs 방식을 통한 탐색]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Queue<int[]> q = new LinkedList<>();
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static boolean chk;
static char list[][];
static int N, M;
static void print() {
if (chk) {
System.out.println(0);
return;
}
StringBuffer sb = new StringBuffer();
sb.append("1\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sb.append(list[i][j]);
}
sb.append("\n");
}
System.out.println(sb.toString());
}
static void func() {
while (!q.isEmpty()) {
int x = q.peek()[0];
int y = q.peek()[1];
q.remove();
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (list[nx][ny] == 'S' || list[nx][ny] == 'D')
continue;
if (list[nx][ny] == 'W') {
chk = true;
break;
}
list[nx][ny] = 'D';
}
if (chk)
break;
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
list = new char[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
for (int j = 0; j < M; j++) {
if (list[i][j] == 'S') {
q.add(new int[] { i, j });
}
}
}
}
public static void main(String[] args) throws Exception {
input();
func();
print();
}
}
|
cs |
[2중 for문을 통한 탐색]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static char list[][];
static int N, M;
static boolean chk;
static void print() {
if (chk) {
System.out.println(0);
return;
}
StringBuffer sb = new StringBuffer();
sb.append("1\n");
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sb.append(list[i][j]);
}
sb.append("\n");
}
System.out.println(sb.toString());
}
static void func() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (list[i][j] == 'S') {
for (int k = 0; k < 4; k++) {
int nx = i + direct[k][0];
int ny = j + direct[k][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (list[nx][ny] == 'S' || list[nx][ny] == 'D')
continue;
if (list[nx][ny] == 'W') {
chk = true;
return;
}
list[nx][ny] = 'D';
}
}
}
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
list = new char[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
}
}
public static void main(String[] args) throws Exception {
input();
func();
print();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 2606 바이러스 (0) | 2021.02.03 |
|---|---|
| boj 1012 유기농 배추 (0) | 2021.02.03 |
| boj 20419 화살표 미로 (Easy) (0) | 2021.01.23 |
| boj 2638 치즈 (0) | 2021.01.22 |
| boj 17142 연구소 3 (0) | 2021.01.22 |