문제:
풀이:
최소 몇번 움직여야하는지 맞춰야 하는 문제이다.
이를 dfs로 풀게되면 모든 경우의 수를 다 살펴봐야하지만,
bfs로 풀면 가장 처음 목적지에 도착할때, 그 횟수를 반환해 줄 수 있다.
동전이 움직일때 꼭 고려해야 하는 사항은 두개이다.
- 동전의 움직임을 기록하고, 중복된 위치에 동전이 있지 않게 해준다.
- 두 동전의 지금 위치를 기록한다.
1 2 - 두 동전의 위치를 바꿔서 기록한다.
2 1 - 두 동전이 각 동전의 자리에 한번에 모여있는 상황을 기록한다.
1, 2
- 두 동전의 지금 위치를 기록한다.
- 두 동전이 동시에 판 밖으로 떨어지면 안된다.
또한 동전은 4방향으로 움직일 수 있으니, 4방향 탐색법을 이용하면 된다. 아래 static 메서드를 이용하도록 하자.
static int[][] move = {{1,0}, {-1, 0}, {0, 1}, {0, -1}};
이번 풀이에서는 클래스를 보다 적극적으로 활용하도록 할 것이다.
이 문제에서 중요한 것은 판의 생김새, 동전의 움직임이다.
각각을 클래스로 분리해주도록 하자.
class Coin {
int y;
int x;
Coin(int y, int x) {
this.y = y;
this.x = x;
}
public Coin move(int dy, int dx, Board board) {
int nextY = y + dy;
int nextX = x + dx;
if (board.isOutOfBounds(nextY, nextX)) {
return null; // 경계를 벗어나면 null 반환
}
if (board.isWall(nextY, nextX)) {
return new Coin(y, x); // 벽을 만나면 이동하지 않음
}
return new Coin(nextY, nextX); // 새로운 위치 반환
}
}위 클래스는 동전의 위치, 움직임을 나타낸다.
move() 메서드에서는 Board 클래스를 이용해 받아온 정보를 적극 활용한다.
class Board {
char[][] board;
boolean[][][][] visited;
int N, M;
Board(char[][] board, int N, int M) {
this.board = board;
this.N = N;
this.M = M;
visited = new boolean[N][M][N][M];
}
boolean isOutOfBounds(int y, int x) {
return y < 0 || y >= N || x < 0 || x >= M;
}
boolean isWall(int y, int x) {
return board[y][x] == '#';
}
boolean isVisited(Coin coin1, Coin coin2) {
return visited[coin1.y][coin1.x][coin2.y][coin2.x];
}
void markVisited(Coin coin1, Coin coin2) { // 중복 방지
visited[coin1.y][coin1.x][coin2.y][coin2.x] = true;
visited[coin2.y][coin2.x][coin1.y][coin1.x] = true;
visited[coin1.y][coin1.x][coin1.y][coin1.x] = true;
visited[coin2.y][coin2.x][coin2.y][coin2.x] = true;
}
}위 클래스에서는 판의 생김새, 그동안 동전이 이동한 기록을 저장한다.
각 메서드는 동전이 다음 위치로 이동할 수 있는지 판정하기 위해 사용된다.
이렇게 클래스를 이용해 동전의 위치, 판의 생김새, 그동안 동전이 이동한 기록을 알 수 있다면,
위 클래스들을 이용한 메서드를 작성할 수 있을 것이다.
static int dropCoin(Coin[] coins, Board board) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{coins[0].y, coins[0].x, coins[1].y, coins[1].x, 0}); // 코인 위치, 이동 횟수 기록
board.markVisited(coins[0], coins[1]); // 첫 위치 기록
while (!queue.isEmpty()) {
int[] now = queue.poll();
int coin1Y = now[0];
int coin1X = now[1];
int coin2Y = now[2];
int coin2X = now[3];
int count = now[4];
if (count == 10) {
return -1;
}
for (int i = 0; i < 4; i++) {
Coin nextCoin1 = new Coin(coin1Y, coin1X);
Coin nextCoin2 = new Coin(coin2Y, coin2X);
// 두 코인 모두 움직여봄
nextCoin1 = nextCoin1.move(move[i][0], move[i][1], board);
nextCoin2 = nextCoin2.move(move[i][0], move[i][1], board);
if ((nextCoin1 == null && nextCoin2 != null )
|| (nextCoin1 != null && nextCoin2 == null)) { // 둘 중 하나 떨어짐
return count + 1;
}
if (nextCoin1 != null && nextCoin2 != null) { // 둘다 떨어지지 않은 경우
if (!board.isVisited(nextCoin1, nextCoin2)) {
board.markVisited(nextCoin1, nextCoin2);
queue.add(new int[]{nextCoin1.y, nextCoin1.x, nextCoin2.y, nextCoin2.x, count + 1});
}
}
}
}
return -1; // queue가 비면 -1 반환(경우의 수 없음)
}위 메서드는 bfs와 Coin, Board 클래스를 이용하여 작성된 메서드이다. 작동 방식은 아래와 같다.
- 두 동전의 처음 위치 정보와, 이동 횟수(0)을 queue에 저장하고, 위치를 기록한다.
- 큐가 비기 전까지 아래 과정을 반복한다.
- queue.poll을 이용해, 동전의 위치, 이동 횟수를 가져온다.
- 만약 이동 횟수가 10번이라면 -1을 반환한다.
bfs 특성상 queue에 저장된 깊이는 지금 보고있는 깊이보다 깊을 수 없기 때문이다. - 두 코인을 각각 4방향으로 움직여본다.
- 움직여본 결과, 둘 중 하나가 떨어진다면, 지금 이동 횟수 + 1을 반환한다.
- 둘 다 떨어지지 않았고, 이미 이동한적 있는 위치가 아니라면,
queue에 두 동전의 위치와 이동횟수 + 1을 저장해준다.
- 큐가 빌 동안 반환이 이뤄지지 않았다면, -1을 반환한다.
두 동전중 한 동전만 먼저 떨어지는 경우는 없다는 말이다.
전체코드:
import java.io.*;
import java.util.*;
// Coin 클래스는 동전의 위치, 움직임을 담당
class Coin {
int y;
int x;
Coin(int y, int x) {
this.y = y;
this.x = x;
}
public Coin move(int dy, int dx, Board board) {
int nextY = y + dy;
int nextX = x + dx;
if (board.isOutOfBounds(nextY, nextX)) {
return null; // 경계를 벗어나면 null 반환
}
if (board.isWall(nextY, nextX)) {
return new Coin(y, x); // 벽을 만나면 이동하지 않음
}
return new Coin(nextY, nextX); // 새로운 위치 반환
}
}
// Board 클래스는 판의 모양, 기록를 알려줌
class Board {
char[][] board;
boolean[][][][] visited;
int N, M;
Board(char[][] board, int N, int M) {
this.board = board;
this.N = N;
this.M = M;
visited = new boolean[N][M][N][M];
}
boolean isOutOfBounds(int y, int x) {
return y < 0 || y >= N || x < 0 || x >= M;
}
boolean isWall(int y, int x) {
return board[y][x] == '#';
}
boolean isVisited(Coin coin1, Coin coin2) {
return visited[coin1.y][coin1.x][coin2.y][coin2.x];
}
void markVisited(Coin coin1, Coin coin2) { // 중복 방지
visited[coin1.y][coin1.x][coin2.y][coin2.x] = true;
visited[coin2.y][coin2.x][coin1.y][coin1.x] = true;
visited[coin1.y][coin1.x][coin1.y][coin1.x] = true;
visited[coin2.y][coin2.x][coin2.y][coin2.x] = true;
}
}
public class Main {
static int[][] move = {{1,0}, {-1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 행
int M = Integer.parseInt(st.nextToken()); // 열
Coin[] coins = new Coin[2];
char[][] board = new char[N][M];
int coinIndex = 0;
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
board[i][j] = line.charAt(j);
if (board[i][j] == 'o') { // 동전 발견 시 위치 저장
coins[coinIndex] = new Coin(i, j);
coinIndex++;
}
}
}
Board realBoard = new Board(board, N, M);
System.out.println(dropCoin(coins, realBoard));
}
static int dropCoin(Coin[] coins, Board board) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{coins[0].y, coins[0].x, coins[1].y, coins[1].x, 0}); // 코인 위치, 이동 횟수 기록
board.markVisited(coins[0], coins[1]); // 첫 위치 기록
while (!queue.isEmpty()) {
int[] now = queue.poll();
int coin1Y = now[0];
int coin1X = now[1];
int coin2Y = now[2];
int coin2X = now[3];
int count = now[4];
if (count == 10) {
return -1;
}
for (int i = 0; i < 4; i++) {
Coin nextCoin1 = new Coin(coin1Y, coin1X);
Coin nextCoin2 = new Coin(coin2Y, coin2X);
// 두 코인 모두 움직여봄
nextCoin1 = nextCoin1.move(move[i][0], move[i][1], board);
nextCoin2 = nextCoin2.move(move[i][0], move[i][1], board);
if ((nextCoin1 == null && nextCoin2 != null )
|| (nextCoin1 != null && nextCoin2 == null)) { // 둘 중 하나 떨어짐
return count + 1;
}
if (nextCoin1 != null && nextCoin2 != null) { // 둘다 떨어지지 않은 경우
if (!board.isVisited(nextCoin1, nextCoin2)) {
board.markVisited(nextCoin1, nextCoin2);
queue.add(new int[]{nextCoin1.y, nextCoin1.x, nextCoin2.y, nextCoin2.x, count + 1});
}
}
}
}
return -1; // queue가 비면 -1 반환(경우의 수 없음)
}
}
시행착오:
처음에는 클래스를 이용하지 않고 풀었고 아래와 같은 풀이가 나왔다.
더보기
import java.io.*;
import java.util.*;
public class Main {
static int[][] move = {{1,0}, {-1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 행
int M = Integer.parseInt(st.nextToken()); // 열
int[][] coins = new int[2][2];
char[][] board = new char[N][M];
int coinIndex = 0;
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
board[i][j] = line.charAt(j);
if (board[i][j] == 'o') { // 동전 발견 시 위치 저장
coins[coinIndex][0] = i;
coins[coinIndex][1] = j;
coinIndex++;
}
}
}
System.out.println(dropCoin(coins, board, N, M));
}
static int dropCoin(int[][] coins, char[][] board, int N, int M) {
boolean[][][][] visited = new boolean[N][M][N][M];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{coins[0][0], coins[0][1], coins[1][0], coins[1][1], 0});
visited[coins[0][0]][coins[0][1]][coins[1][0]][coins[1][1]] = true;
visited[coins[0][0]][coins[0][1]][coins[0][0]][coins[0][1]] = true;
visited[coins[1][0]][coins[1][1]][coins[1][0]][coins[1][1]] = true;
while (!queue.isEmpty()) {
int[] now = queue.poll();
int firstY = now[0];
int firstX = now[1];
int secondY = now[2];
int secondX = now[3];
int count = now[4];
if (count == 10) {
return -1;
}
for (int i = 0; i < 2; i++) {
int nextFirstY = firstY + move[i][0];
int nextSecondY = secondY + move[i][0];
if (nextFirstY == N || nextFirstY < 0) {
if (nextSecondY < N && nextSecondY >= 0) {
return count + 1;
}
continue;
} else if (nextSecondY == N || nextSecondY < 0) {
return count + 1;
}
if (board[nextFirstY][firstX] == '#') {
nextFirstY = firstY;
}
if (board[nextSecondY][secondX] == '#') {
nextSecondY = secondY;
}
if (!visited[nextFirstY][firstX][nextSecondY][secondX]) {
visited[nextFirstY][firstX][nextSecondY][secondX] = true;
visited[nextFirstY][firstX][nextFirstY][firstX] = true;
visited[nextSecondY][secondX][nextSecondY][secondX] = true;
queue.add(new int[]{nextFirstY, firstX, nextSecondY, secondX, count+1});
}
}
for (int i = 2; i < 4; i++) {
int nextFirstX = firstX + move[i][1];
int nextSecondX = secondX + move[i][1];
if (nextFirstX == M || nextFirstX < 0) {
if (nextSecondX < M && nextSecondX >= 0) {
return count + 1;
}
continue;
} else if (nextSecondX == M || nextSecondX < 0) {
return count + 1;
}
if (board[firstY][nextFirstX] == '#') {
nextFirstX = firstX;
}
if (board[secondY][nextSecondX] == '#') {
nextSecondX = secondX;
}
if (!visited[firstY][nextFirstX][secondY][nextSecondX]) {
visited[firstY][nextFirstX][secondY][nextSecondX] = true;
visited[firstY][nextFirstX][firstY][nextFirstX] = true;
visited[secondY][nextSecondX][secondY][nextSecondX] = true;
queue.add(new int[]{firstY, nextFirstX, secondY, nextSecondX, count+1});
}
}
}
return -1;
}
}길이차이가 크지않고, 속도도 크게 다르지 않지만,
너무 하나의 메서드에 책임이 많다. 동전의 이동, 다음칸이 이동할 수 있는 칸인지, 동전 하나만 떨어졌는지를
모두 하나의 메서드에서 책임져야 한다.
이는 객체지향 설계의 원칙 중 단일 책임 원칙을 위배한다.
물론 당장의 속도차이는 나지 않지만, 만일 어떤 프로젝트에서 이런 코드를 작성하게 된다면,
유지보수성, 가독성이 떨어지게 될 것이다.
면접을 준비하며 느낀건데, 확실히 그동안 CS 공부가 부족했던 것 같다.
CS 공부를 병행하며 이론에 맞는 코드를 작성하는 습관을 들여야겠다.
'알고리즘 > 백준' 카테고리의 다른 글
| 1005번 - ACM Craft(비순환 그래프) (0) | 2024.09.29 |
|---|---|
| 9470번 - Strahler 순서(비순환 그래프) (1) | 2024.09.28 |
| 2023번 - 신기한 소수(bfs, 백트래킹) (0) | 2024.09.20 |
| 12969번 - ABC(bfs, dp) (1) | 2024.09.13 |
| 10942번 - 팰린드롬?(dp, br, st) (0) | 2024.09.12 |
