Algorithm/그래프 탐색

BOJ#1525 퍼즐

밤이2209 2017. 5. 4. 18:41

BOJ#1525 퍼즐


* 문제

https://www.acmicpc.net/problem/1525



* 풀이

종만북을 참고하여 풀었습니다.
To-Do : bfs, 양방향탐색, dfs 방법으로 각각 풀어보기

저는 이번에 bfs와 비트마스크를 이용해보았습니다.

맵은 하나의 정점으로 볼 수 있습니다.  (총 정점의 수는 9! : 1부터 9까지 순서대로 나열하는 경우의 수와 같다)

그리고 상하좌우 4방향으로 이동할 수 있으니, 한 정점에서 최대 4개의 정점과 연결될 수 있습니다.
즉, 주어진 정점에서 시작하여 4방향 탐색을 해나가면서 목표를 찾으면 되겠습니다.

문제는 어떻게 중복 방문을 체크하고 처리할 것인지 생각해봐야 합니다.
저는 비트마스크를 이용해보았습니다.

각 값은 0부터 8사이의 값이므로, 각 값은 4비트를 사용하면 저장할 수 있습니다.
비트마스크를 사용하여 맵의 상태를 long 변수에 담아봅시다.

1 3
425
786
위 맵을 비트마스크를 이용하여 표현해보면
000100000011010000100101011110000110 이 됩니다.

보기쉽게 분리해보면
0001 0000 0011

0100 0010 0101

0111 1000 0110

, 이 상태에서 4방향 탐색을 해봅시다. 현재 빈칸의 위치가 row=0, col=1이므로 좌/우/아래의 3가지 탐색만 가능할 것입니다.

1. 좌
0000 0001 0011 
0100 0010 0101
0111 1000 0110

2. 우
0001 0011 0000 
0100 0010 0101 
0111 1000 0110

3. 아래
0001 0010 0011 
0100 0000 0101 
0111 1000 0110


* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231525_Puzzle/src/Main.java


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
* BOJ#1525 퍼즐
* https://www.acmicpc.net/problem/1525
*/

public class Main {

static final int SIZE = 3;

// left, up, right, down
static final int[] dRow = {0, -1, 0, 1};
static final int[] dCol = {-1, 0, 1, 0};
static final long[] dShift = {-4, -12, 4, 12};

public static void main(String[] args) throws IOException {

int row = -1, col = -1;
// 현재 map, 종료 map
long state = 0L, endState = 0L;
HashSet<Long> discovered = new HashSet<>();

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

for (int i = 0; i < SIZE; i++) {

StringTokenizer st = new StringTokenizer(br.readLine());

for (int j = 0; j < SIZE; j++) {

int number = Integer.parseInt(st.nextToken());

if (number == 0) {

row = i;
col = j;
}

state <<= 4;
state |= number;
}
}

for (int i = 1; i < 9; i++) {

endState <<= 4;
endState |= i;
}
endState <<= 4;

// solve - bfs

// 이동횟수
int cnt = -1;

Queue<Point> queue = new LinkedList<>();

queue.add(new Point(row, col, state));
discovered.add(state);

while (!queue.isEmpty()) {

cnt++;

int size = queue.size();
for (int i = 0; i < size; i++) {

Point u = queue.poll();

// 종료 조건
if (u.state == endState) {

System.out.println(cnt);
return;
}

// 4방향 탐색
for (int j = 0; j < 4; j++) {

int nextRow = u.row + dRow[j];
int nextCol = u.col + dCol[j];

// map 범위를 벗어나는 경우
if (nextRow < 0 || nextRow > 2 || nextCol < 0 || nextCol > 2) continue;

// nextState 계산

// 제거할 퍼즐 조각 위치 (0~8) : nextRow, nextCol -> nextPos
long nextPos = 8 - ((nextRow * 3) + nextCol);

// 제거할 퍼즐 조각
long piece = u.state & (15L << (nextPos * 4));

// 제거한다
long nextState = u.state - piece;

// 제거한 퍼즐 조각을 현재 위치에 추가한다
if (dShift[j] > 0) piece <<= dShift[j];
else piece >>= -dShift[j];

nextState += piece;

// nextState를 이미 방문한 경우
if (discovered.contains(nextState)) continue;

// nextState를 방문하지 않은 경우
discovered.add(nextState);
queue.add(new Point(nextRow, nextCol, nextState));
}
}
}

System.out.println(-1);
}
}

class Point {

int row, col;
long state;

Point(int row, int col, long state) {

this.row = row;
this.col = col;
this.state = state;
}
}




'Algorithm > 그래프 탐색' 카테고리의 다른 글

BOJ#10216 Count Circle Groups  (0) 2017.07.24
BOJ#10429 QUENTO  (0) 2017.06.01
BOJ#14502 연구소  (0) 2017.04.25
BOJ#14500 테트로미노  (0) 2017.04.21
BOJ#1600 말이 되고픈 원숭이  (0) 2017.04.19