문제#
- 링크로 대체
풀이 및 주저리..
시뮬레이션적인 부분과 중요한 DFS 적인 부분이 섞여있는 문제였다. 결국 맵과 처음의 동전 위치를 구해준 후 움직이면서 정답을 찾는 문제인데, 정답인 상황과 정답이 아닌 상황을 처리해주는 부분이 어려웠던 것 같다. 처음에는 동전이 하나 떨어진 이후에 움직이는 상황까지 고려하거나 이상한 상황을 가정했는데, 생각해보면 다 무의미한 가정이였다. (동전이 하나만 떨어진 경우 정답이니깐..) 동전을 떨어뜨릴 수 없는 상황에서의 처리도 꽤 힘들었던 것 같다. 재귀에서 매번 전역변수를 사용해서 답을 찾거나 하는 경우가 많다보니 return 값으로 처리하는 부분을 깔끔하게 처리하지 못했던 것 같다.
결국 아직 부족한건 머리속에서 생각하는 것을 코드로 잘 옮기지 못하는 것에 있는 것 같다. 더 많이 연습해서 익숙해지자!
코드가 깔끔하지 못해서 마음에 많이 걸리는데.. 아마 오프라인 수업중에 풀었던 문제를 한번 쭉 풀어본 뒤 다시 처음부터 쭉 풀어볼 예정이니, 다시 돌아올 때는 좀더 깔끔하게 풀 수 있는 실력이 되어있으면 좋을 것 같다.
먼저 일하는 날과 얻을 수 있는 수익을 배열로 만들어 저장해 두고 DPS 로 문제를 풀었다. 풀고나서 구글링 해보니 DP 로도 풀 수 있는 문제인 것 같은데, 좀 더 고민하고 후에 다시 도전해봐야겠다.
코드
package baekjoon.algorithm.day03;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class TwoCoin {
static final int[] dx = { 0, 0, -1, 1 };
static final int[] dy = { -1, 1, 0, 0 };
static int answer = -1;
static int N, M;
static char[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
map = new char[N][M];
Queue<Integer> coinQue = new LinkedList<Integer>();
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = line.charAt(j);
if (map[i][j] == 'o') {
// 동전위치면 큐에 넣어줌
coinQue.add(i);
coinQue.add(j);
}
}
}
go(coinQue.poll(), coinQue.poll(), coinQue.poll(), coinQue.poll(), 0);
System.out.println(answer);
}
public static int go(int x1, int y1, int x2, int y2, int index) {
if (index == 11) {
return -1;
}
boolean isOneFall = false, isTwoFall = false;
if (x1 < 0 || x1 >= N || y1 < 0 || y1 >= M)
isOneFall = true;
if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= M)
isTwoFall = true;
if (isOneFall && isTwoFall)
return -1;
if (isOneFall || isTwoFall)
return index;
for (int i = 0; i < 4; i++) {
int tX1 = x1 + dx[i];
int tY1 = y1 + dy[i];
int tX2 = x2 + dx[i];
int tY2 = y2 + dy[i];
if (tX1 >= 0 && tX1 < N && tY1 >= 0 && tY1 < M && map[tX1][tY1] == '#') {
tX1 = x1;
tY1 = y1;
}
if (tX2 >= 0 && tX2 < N && tY2 >= 0 && tY2 < M && map[tX2][tY2] == '#') {
tX2 = x2;
tY2 = y2;
}
int temp = go(tX1, tY1, tX2, tY2, index + 1);
if (temp == -1)
continue;
if (answer == -1 || answer > temp)
answer = temp;
}
return answer;
}
}기억에 남길 것!
- 문제의 정답처리를 잘 이해하자!