HANCO
SWEA.1226 미로1 [JAVA] [D4] 본문
비도 오고 심심해서 카페에 앉아 오랜만에 탐색알고리즘 공부의 기본이 되는 문제인 미로탐색 문제를 풀어보았다.
이 문제는 백준에서는 아마 미로탐색이라는 문제 일 것이다.
SWAE 링크는 아래와 같다.
알고리즘 공부를 처음 할때 이런 문제를 볼 때 매우 당황하며 풀기 싫을 수 있다. (마치 처음 보는 수학문제를 접하는 느낌)
허나, 매우 매우 기본이 되는 탐색 알고리즘 다들 알 것이다. BFS, DFS로 이 문제를 간단하게 풀 수도 있다.
미로1 문제는 단순히 공식을 외워서 적기만 해도 풀리는 문제이다.
일단 그 이유를 쉽게 설명하자면 문제의 의도가 탈출의 가능 여부를 묻기 때문이다. (탈출이 가능하면 1 / 탈출이 불가능 하면 0)
미로탐색문제를 접하다보면 이런 유형 말고 실제 탐색을 완료했을 때 최소 이동 횟수를 구하는 탐색 알고리즘이 있을 것이다. 그 문제는 이렇게 단순히 기본알고리즘 공식으로만으로 풀 수가 없다. 물론, 테스트케이스 운이 좋으면 풀릴 수도 있다. 하지만 우리는 항상 최악의 경우를 고려해야하는 개발자이므로 그냥 불가능하다고 말하겠다.
무튼, 이 문제는 기본 탐색알고리즘을 사용해서 풀어 볼것이고 위의 다른 유형의 문제는 다른 포스팅에서 올리도록 하겠다.
평소 알고리즘문제를 풀때엔 C++을 써야한다는 약간의 강박이 있어서 지금껏 C++을 써왔지만 최근 자바를 공부해야하기도 하고 자바 문법을 조금씩 익힐겸(겸사겸사) 자바로 이 문제를 풀어보았다.
문제 설명을 위한 포스팅으로 BFS의 개념은 어느정도 알고 있다고 생각하고 글을 쓰겠다.
코드를 보기 전에 아직 자바문법에 대한 효율성 보다는 자바에 있는 라이브러리등을 써보는데 의의를 두고 코드를 작성했다는 것을 알아 두길 바란다.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* 1226 미로1
*/
public class sw1226 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 이동할 좌표값
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
//10번실행
for(int tc=1;tc<=10;tc++) {
Queue<Move> q = new LinkedList<Move>();
// 16*16 map init
int [][] map = new int[16][16];
boolean [][] chk = new boolean[16][16];
int t = sc.nextInt();
Move st = new Move();
Move et = new Move();
for(int i=0;i<16;i++) {
// str 입력
String str = sc.next();
// sb에 할당
for(int j=0;j<16;j++) {
map[i][j] = str.charAt(j)-'0';
if((int) str.charAt(j)-'0' == 2) {
st = new Move(i, j);
//구조체 삽입
}
if((int) str.charAt(j)-'0' == 3) {
et = new Move(i, j);
}
}
}
boolean res = new Boolean(false);
q.add(st);
chk[st.x][st.y] = true;
while(!q.isEmpty()) {
Move now = new Move();
now = q.poll();
if(map[now.x][now.y] == 3) {
res = true;
break;
}
for(int i=0;i<4;i++) {
Move next = new Move();
next.x = now.x + dx[i];
next.y = now.y + dy[i];
if(next.x <= 0 || next.y <= 0 || next.x >= 15 || next.y >= 15) continue;
if(chk[next.x][next.y] == true) continue;
if(map[next.x][next.y] == 1) continue;
q.add(next);
chk[next.x][next.y] = true;
}
}
System.out.print("#" + t + " ");
System.out.println(res == true ? '1' : '0');
}
}
}
class Move {
int x;
int y;
public Move() {
}
public Move(int x, int y) {
this.x = x;
this.y = y;
}
}[코드설명]
자바를 오랜만에 하다보니 입력을 받는 부분 부터가 나에게는 고난이었다.
c++이었다면 scanf("%1d", &input) << - 이런 식으로 붙어있는 스트링 개별문자를 가져와 받아올 수 있지만 자바라서 스트링을 받아와 배열 인덱스를 이용해 접근하여 값을 2차원 배열에 저장하였다. 그부분이 아래와 같다.
for(int i=0;i<16;i++) {
// str 입력
String str = sc.next();
// sb에 할당
for(int j=0;j<16;j++) {
// 아스키 코드값 '0'을 빼주는 것이 매우 중요하다 이렇게 하면 문자를 숫자로 받아서 사용할 수 있다.
map[i][j] = str.charAt(j)-'0';
// 시작지점과 도착지점을 구조체 객체에 저장해 주었다. (st, et);
// 시작 지점 저장
if((int) str.charAt(j)-'0' == 2) {
st = new Move(i, j);
}
// 도착 지점 저장
if((int) str.charAt(j)-'0' == 3) {
et = new Move(i, j);
}
}
}그 이후에는 BFS문법을 사용해서 문제를 풀어보았다.
// 처음 큐에 값을 넣어 주고
q.add(st);
chk[st.x][st.y] = true;
// 큐가 빌때까지 반복문을 돌린다.
while(!q.isEmpty()) {
// 현제 큐의 맨위에 있는 값을 반환하면서 진행
Move now = new Move();
now = q.poll();
// 만약 3을 만난다면
if(map[now.x][now.y] == 3) {
res = true;
break;
}
// 4방 탐색을 위한 반복문이다.
// BFS에서 4방탐색을 하는 기본 알고리즘
for(int i=0;i<4;i++) {
Move next = new Move();
next.x = now.x + dx[i];
next.y = now.y + dy[i];
// 배열값을 넘어가거나 방문했거나 벽으로 막혀있다면 무시하고 continue실행
if(next.x <= 0 || next.y <= 0 || next.x >= 15 || next.y >= 15) continue;
if(chk[next.x][next.y] == true) continue;
if(map[next.x][next.y] == 1) continue;
// 만약 위의 조건을 만족하지 않는다면 큐에 넣어주고 방문체크를 해준다.
q.add(next);
chk[next.x][next.y] = true;
}
}이 부분은 객체 클래스
class Move {
int x;
int y;
public Move() {
}
public Move(int x, int y) {
this.x = x;
this.y = y;
}
}노트 저장 완료!