https://www.acmicpc.net/problem/1525
1525호: 직소 퍼즐
3줄 표에 입력된 9개의 숫자를 얻습니다. 한 줄에 세 개의 숫자가 주어지고 빈 셀은 0으로 표시됩니다.
www.acmicpc.net
bfs로 해결할 수 있습니다.
주요 포인트
2차원 배열을 일렬로 놓고 값 자체로 판단하면 쉽게 구할 수 있다.
값의 위치를 변경할 때 각각의 인덱스를 알아야 하는데 이 경우 StringBuilder를 이용하면 쉽게 위치를 변경할 수 있습니다.
StringBuilder.setCharAt -> 특정 위치에 문자를 삽입합니다.할수있다.
이것을 이용해서 해결해 봅시다.
올바른 응답 코드
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
public class Main{
public static void main(String() args) {
Scanner sc = new Scanner(System.in);
int value = 0;
for (int i = 0; i < 9; i++){
int v = sc.nextInt();
if (v==0)v = 9;
value = (value*10) + v;
}
Map<Integer, Integer> map = new HashMap<>();
Queue<Integer> q = new LinkedList<>();
map.put(value,0);
q.offer(value);
int() dy = {1,0,-1,0};
int() dx = {0,-1,0,1};
while (!q.isEmpty()){
int nowNum = q.poll();
String now = String.valueOf(nowNum);
int nineIndex = now.indexOf("9");
int y = nineIndex/3;
int x = nineIndex%3;
for (int i = 0; i < 4; i++){
int ny = y + dy(i);
int nx = x + dx(i);
int move = ny*3+nx;
if (0<= ny && ny <3 && 0<= nx && nx <3){
StringBuilder sb = new StringBuilder(now);
char temp = sb.charAt(move);
sb.setCharAt(move,'9');
sb.setCharAt(nineIndex,temp);
int next = Integer.parseInt(sb.toString());
if (!map.containsKey(next)){
map.put(next, map.get(nowNum)+1);
q.offer(next);
}
}
}
}
if (map.containsKey(123456789)) {
System.out.println(map.get(123456789));
} else {
System.out.println(-1);
}
}
}논평
입력한 값을 정렬하기 위해 값을 한 칸 늘립니다. -> 값 = 값*10 + v;
또한 이미 변경된 조합을 만들 필요 없이 각 카운트에 대해 하나의 카드를 사용하면 됩니다.
큐는 bfs에 대해 선언됩니다.
현재 저장된 값에서 위치 9를 검색합니다.
해당 위치를 사용하여 현재 x, y 좌표를 찾고 해당 좌표에서 멀어지는 위치를 찾습니다.
바꿀 수 있는 경우 원래 9의 위치를 해당 위치에 해당하는 문자로 바꿉니다.
이 시점에서 StringBuilder.setCharAt()를 사용하여 쉽게 변경할 수 있습니다.
해당 값이 맵에 이미 존재하는 경우 값이 삽입되지 않습니다.
마지막으로 123456789가 우리가 원하는 것인지 확인한 후 출력해 봅시다.
배우다
이 문제를 보았을 때 처음에는 이해하지 못했습니다.
이 문제를 해결한 것은 이번이 처음이고, 그것을 보았을 때 아이디어가 즉시 떠오르지 않았습니다.
솔루션을 볼 때 고려해야 할 몇 가지 사항이 있었습니다. 지도로 bfs를 하는 것은 새로운 경험이었습니다.
StringBuilder의 메서드를 사용할 수 있다는 점에서도 새롭습니다.