문제 탐색하기
입력 자료 정리
- N은 평지의 가로 세로 길이다
- 이어서 들어오는 값은 문자열을 포함한 값으로 N X N의 입력값이다
- 0은 빈칸, 1은 다른 나무, B는 통나무 E는 종료지점이다
- 0은 이동할 수 있으며 1은 이동할 수 없다
- B와 E는 같은방향으로 3번 연속되어 나타난다
해결방법 추론
- 입력 최대 크기도 작고 가능한 최소 동작횟수를 구하는 문제이므로 bfs탐색에 주어진 조건에 맞춰서 해결하는 구현문제라고 생각했다
- 통나무를 잘 관리해서 BFS탐색으로 종료지점에 딱 맞게 움직인다면 정답을 찾을 수 있을 것이다
- 다만 통나무가 3칸이라서 조금 관리가 까다롭다. 따라서 중간 위치만 보관하고, 나머지는 상하좌우 이동할 때나 회전할때, 그리고 종료지점 체크할 때 중간지점을 기준으로 그 양옆을 확인하기로 결정했다
- 이어서 방향도 기억하고 있어야한다. 통나무의 방향은 가로방향과 세로방향만 가능하다
- 이 두가지를 잘 기억하고 실수없이 구현한다면 정답을 구할 수 있을 것이다
시간복잡도 계산
- 시간복잡도는 BFS 탐색에서 정점 N^2과 상수의 간선을 탐색하므로
O(N^2)이 된다 - 따라서 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리
- n은 int형 변수에 관리한다
- arr배열은 char형 2차원 배열로 선언하며 크기는 n x n이다
- 통나무가 있는 지점과 종료지점을 구해야한다. 2차원 배열도 좋지만 이번에는 Pos라는 별도의 클래스를 만들었다. 이번에도 x와 y를 뒤집었다!
- 두 지점 모두 3칸 좌표를 가지므로 크기를 3으로 하는 Pos타입의 배열로 선언했다
- B일때는 시작지점에 E일 때는 종료지점에 좌표를 넣어준다
- 또한 4방 탐색 편의 배열도 BFS 탐색을 위해 선언한다
- bfs 탐색 결과를 ans에 담는다.
BFS 구현 설계
- 방문배열을 3차원으로 선언한다. 2xnxn 크기로 방향-x-y값 순이다
- 현재 방향을 파악하기 위해 시작지점의 0번 인덱스의 y+1이 1번 인덱스의 1과 같은지 확인한다
- 만약 같다면 가로 방향으로 있는 것이고 0으로 설정한다. 아니라면 세로방향이므로 1로 설정한다
- 시작지점을 넣고 탐색을 시작한다
정답 조건일 경우
- 만약 현재 지점이 종료지점의 중간 지점 좌표와 같다면 방향에 따라 x와 y에 -1, +1한 값을 비교한다
- 두 지점 모두 E라면 지금까지의 거리 탐색 결과를 리턴한다
상하좌우 이동 범위 탐색
- 상하좌우 탐색을 하며, 방문여부와 범위를 벗어나는지 여부를 확인한다
- 만약 모두 통과하면 거리 + 1 한 결과와함께 넣어준다
- 이동범위는 방향에 따라 한번 구분하고, 또 현재 탐색한 방향에 따라 또 구분한다
0,1은 상하 / 1,2는 좌우다. - 가로방향의 통나무일 때, 수평으로 어떻게 이동하는지와 세로방향의 통나무일 때, 수직방향으로 어떻게 이동하는지 생각해서 범위를 벗어나는 경우 false를 리턴한다
- 모두 통과하면 true를 리턴한다
회전여부 탐색
- 회전 여부는 현재 지점으로부터 3x3범위내에 범위를 벗어나거나 1이 있는지 확인하면 된다
- 만약 하나라도 있다면 false를 리턴하고 아니라면 true를 리턴한다
- 회전이 가능하다면 다시 방향과 미방문 여부를 체크해서 구분한다
- 구분한 결과에 따라 현재 방향의 반대 방향으로 넣어주고 거리+1해서 넣어준다.
출력값 설계
- bfs결과를 담은 ans를 출력하면 정답이 된다
정답 코드
import java.io.*;
import java.util.*;
class Pos{
int x;
int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
class Log{
int x;
int y;
int dir;
int dist;
public Log(int x, int y, int dir, int dist) {
this.x = x;
this.y = y;
this.dir = dir;
this.dist = dist;
}
}
public class Main {
static int n;
static char[][] arr;
static Pos[] start;
static Pos[] end;
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));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
arr = new char[n][n];
start = new Pos[3];
end = new Pos[3];
int idx1 = 0;
int idx2 = 0;
for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < n; j++) {
arr[i][j] = s.charAt(j);
if(arr[i][j] == 'B'){
start[idx1++] = new Pos(i, j);
}
if(arr[i][j] == 'E'){
end[idx2++] = new Pos(i, j);
}
}
}
int ans = bfs();
bw.write(ans+"");
br.close();
bw.close();
}
private static int bfs() {
boolean[][][] visited = new boolean[2][n][n];
Queue<Log> q = new LinkedList<>();
int nowDir = -1;
if(start[0].y + 1 == start[1].y){
nowDir = 0;
}else{
nowDir = 1;
}
q.add(new Log(start[1].x, start[1].y, nowDir, 0));
visited[nowDir][start[1].x][start[1].y] = true;
while(!q.isEmpty()){
Log now = q.poll();
if(now.x == end[1].x && now.y == end[1].y){
if(now.dir == 0 && arr[now.x][now.y-1] == 'E' && arr[now.x][now.y+1] == 'E'){
return now.dist;
}else if(now.dir == 1 && arr[now.x-1][now.y] == 'E' && arr[now.x+1][now.y] == 'E'){
return now.dist;
}
}
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if(!isRange(nx,ny,now.dir, i)){
continue;
}
if(visited[now.dir][nx][ny]){
continue;
}
visited[now.dir][nx][ny] = true;
q.add(new Log(nx, ny, now.dir, now.dist+1));
}
if(canRotate(now.x, now.y)){
if(now.dir == 0 && !visited[1][now.x][now.y]){
visited[1][now.x][now.y] = true;
q.add(new Log(now.x, now.y, 1, now.dist+1));
}else if(now.dir == 1 && !visited[0][now.x][now.y]){
visited[0][now.x][now.y] = true;
q.add(new Log(now.x, now.y, 0, now.dist+1));
}
}
}
return 0;
}
private static boolean canRotate(int x, int y) {
for (int i = x-1; i <= x + 1; i++) {
for (int j = y-1; j <= y + 1; j++) {
if(i < 0 || i >= n || j < 0 || j >= n){
return false;
}
if(arr[i][j] == '1'){
return false;
}
}
}
return true;
}
private static boolean isRange(int x, int y, int dir, int i) {
switch(dir) {
case 0:
if(i < 2) {
if(x < 0 || x >= n){
return false;
}
if(arr[x][y] == '1' || arr[x][y - 1] == '1' || arr[x][y + 1] == '1'){
return false;
}
}
else {
if(y - 1 < 0 || y + 1 >= n){
return false;
}
if(arr[x][y] == '1' || arr[x][y - 1] == '1' || arr[x][y + 1] == '1'){
return false;
}
}
break;
case 1:
if(i < 2) {
if(x - 1 < 0 || x + 1 >= n){
return false;
}
if(arr[x][y] == '1' || arr[x - 1][y] == '1' || arr[x + 1][y] == '1'){
return false;
}
}
else {
if(y < 0 || y >= n){
return false;
}
if(arr[x][y] == '1' || arr[x - 1][y] == '1' || arr[x + 1][y] == '1'){
return false;
}
}
break;
}
return true;
}
}문제 링크
Software Developer