최소 횟수라는 말을 보고 바로 bfs를 떠올렸다. 큐에 조건에 맞는 동전의 좌표쌍을 넣고 빼는 것을 반복하면서 한 개만 밖으로 나갈 경우 해당 cnt를 출력해주는 식으로 구현하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] dx = {0, -1, 0, 1};
static int[] dy = {1, 0, -1, 0};
static int N, M;
static char[][] map;
static boolean[][][][] visited;
static int sx1, sy1, sx2, sy2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// map 입력받기
int count = 0;
map = new char[N][M];
visited = new boolean[N][M][N][M];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] == 'o') {
if (count == 0) {
sx1 = i;
sy1 = j;
count++;
} else if (count == 1) {
sx2 = i;
sy2 = j;
}
}
}
}
System.out.println(bfs(sx1, sy1, sx2, sy2, 0));
}
public static int bfs(int x1, int y1, int x2, int y2, int cnt) {
Queue<Move> q = new LinkedList<>();
q.add(new Move(x1, y1, x2, y2, cnt));
visited[x1][y1][x2][y2] = true;
while (!q.isEmpty()) {
Move now = q.poll();
if (now.cnt == 10) continue;
for (int i = 0; i < 4; i++) {
int nx1 = now.x1 + dx[i];
int ny1 = now.y1 + dy[i];
int nx2 = now.x2 + dx[i];
int ny2 = now.y2 + dy[i];
// 바깥으로 하나만 나가는 경우
if ((isBorder(nx1, ny1) && !isBorder(nx2, ny2))
|| (!isBorder(nx1, ny1) && isBorder(nx2, ny2))) {
return now.cnt + 1;
}
// 조건에 맞는 경우 큐에 추가 - 1.방문X, 2.둘다 map범위밖X, 3.벽인 경우 보정
if (!isBorder(nx1, ny1) && !isBorder(nx2, ny2)) {
if (map[nx1][ny1] == '#') {
nx1 = now.x1;
ny1 = now.y1;
}
if (map[nx2][ny2] == '#') {
nx2 = now.x2;
ny2 = now.y2;
}
if (!visited[nx1][ny1][nx2][ny2]) {
visited[nx1][ny1][nx2][ny2] = true;
q.add(new Move(nx1, ny1, nx2, ny2, now.cnt + 1));
}
}
}
}
return -1;
}
public static boolean isBorder(int x, int y) {
return (x < 0 || y < 0 || x > N - 1 || y > M - 1);
}
}
class Move {
int x1;
int y1;
int x2;
int y2;
int cnt;
public Move(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;
}
}
bfs도 조건만 잘 잡고 구현하면 크게 오래 걸리지 않는 것 같다.