1525번: 퍼즐
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
www.acmicpc.net
- 생각
입력한 배열에서 0인 곳이 비어있는 곳인데 비어있는 곳에서 상, 하, 좌, 우로 한번씩 움직이면서
1 2 3
4 5 6
7 8 0
처럼 출력이 나오게 만들면 되는 문제이다. (단, 만들지 못할시 -1 출력)
푼 방식은 bfs 방식이다.
배열로 입력을 받으려 했는데 문제가 많았다. (메모리, 시간문제)
변경한 방법은 정수형으로 받아서 hashSet을 사용했다.
hashSet에 지나온 정수형을 모두 추가한다. (ex, 123456789, 312456897) 0이 없는 이유는 01234568로 추가를 하면 1234568로 추가가 되기 때문에 0을 9로 바꾸어 주었다.
위치를 바꿀 수 있는 것은 9의 위치이기 때문에 해당 위치를 찾고 상, 하, 좌, 우 중에서 움직일 수 있는 곳으로 움직인다. (단, hashSet에 추가되어있는 것들은 이미 지나와서 123456789를 만들거나 만들지 못했던 것들이기 때문에 건너띄어준다.)
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class Main {
static int[] x = { -1, 1, 0, 0 };
static int[] y = { 0, 0, -1, 1 };
static int answer, count;
static Set<Integer> check;
static Queue<int[]> queue;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
answer = Integer.MAX_VALUE;
count = 0;
check = new HashSet<Integer>();
queue = new LinkedList<>();
int temp = 0, input = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
input = in.nextInt();
if (input == 0)
input = 9;
temp = temp * 10 + input;
}
}
check.add(temp);
queue.offer(new int[] {temp, 0});
bfs();
if(answer == Integer.MAX_VALUE) answer = -1;
}
private static void bfs() {
int nowNumber[], nowIndex, nowRow, nowColumn, nextNumber;
String nowString;
while (!queue.isEmpty()) {
nowNumber = queue.poll();
if (nowNumber[0] == 123456789)
answer = Math.min(answer, nowNumber[1]);
nowString = String.valueOf(nowNumber[0]);
nowIndex = nowString.indexOf('9');
nowRow = nowIndex / 3;
nowColumn = nowIndex % 3;
for (int direction = 0; direction < 4; direction++) {
int r = nowRow + x[direction];
int c = nowColumn + y[direction];
if (r < 0 || c < 0 || r >= 3 || c >= 3) continue;
int nextIndex = r * 3 + c; // 이동할 index
StringBuilder next = new StringBuilder(nowString);
char temp = next.charAt(nextIndex);
next.setCharAt(nextIndex, '9');
next.setCharAt(nowIndex, temp);
nextNumber = Integer.parseInt(next.toString()); //이동한 값
if(check.contains(nextNumber)) continue;
count++;
check.add(nextNumber);
queue.offer(new int[] {nextNumber, nowNumber[1] + 1});
count--;
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 13460번 : 구슬 탈출 2 (0) | 2021.03.12 |
|---|---|
| [BOJ/JAVA] 백준 17144번 : 미세먼지 안녕! (0) | 2021.03.11 |
| [BOJ/JAVA] 백준 1963번 : 소수 경로 (0) | 2021.03.08 |
| [BOJ/JAVA] 백준 2666번 : 벽장문의 이동 (0) | 2021.03.04 |
| [BOJ/JAVA] 백준 2312번 : 수 복원하기 (0) | 2021.03.03 |
