알고리즘/백준
공부 220-221일차: 백준 16197번 두 동전 자바 java
김발자~
2023. 3. 7. 23:01
반응형
16197 두 동전
https://www.acmicpc.net/problem/16197
16197번: 두 동전
N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고,
www.acmicpc.net
백준 16197번 문제 두 동전
문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 8972 | 3953 | 2682 | 42.410% |
문제
N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.
버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.
- 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
- 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
- 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)
둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.
o: 동전.: 빈 칸#: 벽
동전의 개수는 항상 2개이다.
출력
첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.
예제 입력 1
1 2
oo
예제 출력 1
1
예제 입력 2
6 2
.#
.#
.#
o#
o#
##
예제 출력 2
4
예제 입력 3
6 2
..
..
..
o#
o#
##
예제 출력 3
3
예제 입력 4
5 3
###
.o.
###
.o.
###
예제 출력 4
-1
예제 입력 5
5 3
###
.o.
#.#
.o.
###
예제 출력 5
3
과정 생각해보기 & 오답
틀린 코드 부터..
|
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m, x1, y1, x2, y2;
static int min = Integer.MAX_VALUE;
static char[][] board;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
board = new char[n][m];
for(int i = 0; i < n; i++) {
String str = br.readLine();
for(int j = 0; j < m; j++) {
if(str.charAt(j) == 'o' && x1 == 0) {
x1 = i;
y1 = j;
}else if(str.charAt(j) == 'o' && x1 != 0) {
x2 = i;
y2 = j;
}
board[i][j] = str.charAt(j);
}
}
bfs();
bw.write(min+"");
bw.flush();
bw.close();
br.close();
}
static void bfs() {
Queue<Node> q = new LinkedList<>();
q.add(new Node(x1, y1, x2, y2, 0));
while(!q.isEmpty()) {
Node now = q.poll();
if(now.cnt > 10) {
min = -1;
return;
}
for(int i = 0; i < 4; i++) {
int count = 0;
int X1 = now.x1 + dx[i];
int Y1 = now.y1 + dy[i];
int X2 = now.x2 + dx[i];
int Y2 = now.y2 + dy[i];
if(X1 < 0 || X1 > n-1 || Y1 < 0 || Y1 > m-1) { // 보드 밖으로
count++;
}
if(X2 < 0 || X2 > n-1 || Y2 < 0 || Y2 > m-1) { // 보드 밖으로
count++;
}
if(count == 1) { // 동전 두 개 중 하나만 보드 밖으로
min = Math.min(min, now.cnt+1);
return;
}else if(count == 2) {
continue;
}
if(board[X1][Y1] == '#') { // 벽
X1 = now.x1;
Y1 = now.y1;
}
if(board[X2][Y2] == '#') {
X2 = now.x2;
Y2 = now.y2;
}
q.add(new Node(X1, Y1, X2, Y2, now.cnt+1));
}
}
}
static class Node{
int x1;
int y1;
int x2;
int y2;
int cnt;
Node(int x1, int y1, int x2, int y2, int cnt){
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
this.cnt = cnt;
}
}
}
|
cs |
최솟값을 구하는 문제라 bfs로 풀었다
visited 배열을 만들지 않아도 예제가 모두 맞게 출력되길래 냅뒀는데 실패..ㅜ
|
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
94
95
96
97
98
99
100
101
102
103
104
105
|
public class Main {
static int n, m, x1, y1, x2, y2;
static int min = Integer.MAX_VALUE;
static char[][] board;
static boolean[][][][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
board = new char[n][m];
visited = new boolean[n][m][n][m];
for(int i = 0; i < n; i++) {
String str = br.readLine();
for(int j = 0; j < m; j++) {
if(str.charAt(j) == 'o' && x1 == 0) {
x1 = i;
y1 = j;
}else if(str.charAt(j) == 'o' && x1 != 0) {
x2 = i;
y2 = j;
}
board[i][j] = str.charAt(j);
}
}
bfs();
bw.write(min+"");
bw.flush();
bw.close();
br.close();
}
static void bfs() {
Queue<Node> q = new LinkedList<>();
q.add(new Node(x1, y1, x2, y2, 0));
visited[x1][y1][x2][y2] = true;
while(!q.isEmpty()) {
Node now = q.poll();
for(int i = 0; i < 4; i++) {
int count = 0;
int X1 = now.x1 + dx[i];
int Y1 = now.y1 + dy[i];
int X2 = now.x2 + dx[i];
int Y2 = now.y2 + dy[i];
if(X1 < 0 || X1 > n-1 || Y1 < 0 || Y1 > m-1) { // 보드 밖으로
count++;
}
if(X2 < 0 || X2 > n-1 || Y2 < 0 || Y2 > m-1) { // 보드 밖으로
count++;
}
if(count == 1) { // 동전 두 개 중 하나만 보드 밖으로
min = Math.min(min, now.cnt+1);
return;
}else if(count == 2) {
continue;
}
if(board[X1][Y1] == '#') { // 벽
X1 = now.x1;
Y1 = now.y1;
}
if(board[X2][Y2] == '#') {
X2 = now.x2;
Y2 = now.y2;
}
if(!visited[X1][Y1][X2][Y2]) {
visited[X1][Y1][X2][Y2] = true;
q.add(new Node(X1, Y1, X2, Y2, now.cnt+1));
}
}
}
min = -1;
}
static class Node{
int x1;
int y1;
int x2;
int y2;
int cnt;
Node(int x1, int y1, int x2, int y2, int cnt){
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
this.cnt = cnt;
}
}
}
|
cs |
visited를 만들고, min 갱신이 안 되길래 밑에 적어서 해봤는데 이것도 실패
구글링 해보니 다른 분들 풀이가 워낙 다양해서 내일 다시 해볼 예정
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ어젠 이걸 왜 몰랐지..? 일단 동전을 넣는 코드부터 틀렸다
x1이 0인 경우도 있기 때문.. 그래서 구분하는 변수를 따로 둘까 하다가, 그냥 x1이 절대 가질 수 없는 -1로 초기화했다
bfs는 위와 똑같이 돌린 후 메인 메서드에서 min이 10을 초과하면 -1로 두면 된다
정답 인정 코드
|
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m, y1, x2, y2;
static int x1 = -1;
static int min = Integer.MAX_VALUE;
static char[][] board;
static boolean[][][][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
board = new char[n][m];
visited = new boolean[n][m][n][m];
for(int i = 0; i < n; i++) {
String str = br.readLine();
for(int j = 0; j < m; j++) {
board[i][j] = str.charAt(j);
if(board[i][j] == 'o' && x1 == -1) {
x1 = i;
y1 = j;
}else if(board[i][j] == 'o' && x1 != -1) {
x2 = i;
y2 = j;
}
}
}
bfs();
if(min > 10) {
min = -1;
}
bw.write(min+"");
bw.flush();
bw.close();
br.close();
}
static void bfs() {
Queue<Node> q = new LinkedList<>();
q.add(new Node(x1, y1, x2, y2, 0));
visited[x1][y1][x2][y2] = true;
while(!q.isEmpty()) {
Node now = q.poll();
if(now.cnt > 10 || now.cnt > min) {
return;
}
for(int i = 0; i < 4; i++) {
int count = 0;
int X1 = now.x1 + dx[i];
int Y1 = now.y1 + dy[i];
int X2 = now.x2 + dx[i];
int Y2 = now.y2 + dy[i];
if(X1 < 0 || X1 > n-1 || Y1 < 0 || Y1 > m-1) { // 보드 밖으로
count++;
}
if(X2 < 0 || X2 > n-1 || Y2 < 0 || Y2 > m-1) { // 보드 밖으로
count++;
}
if(count == 1) { // 동전 두 개 중 하나만 보드 밖으로
min = Math.min(min, now.cnt+1);
return;
}
if(count == 2) {
continue;
}
if(board[X1][Y1] == '#') { // 벽
X1 = now.x1;
Y1 = now.y1;
}
if(board[X2][Y2] == '#') {
X2 = now.x2;
Y2 = now.y2;
}
if(!visited[X1][Y1][X2][Y2]) {
visited[X1][Y1][X2][Y2] = true;
q.add(new Node(X1, Y1, X2, Y2, now.cnt+1));
}
}
}
}
static class Node{
int x1;
int y1;
int x2;
int y2;
int cnt;
Node(int x1, int y1, int x2, int y2, int cnt){
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
this.cnt = cnt;
}
}
}
|
cs |
반응형