<Baekjoon> #1525 퍼즐_graph, HashMap java

Google 아니고 Joogle·2022년 9월 13일
0

Baekjoon

목록 보기
46/47

#1525 퍼즐

Solution

  • 문제의 핵심은 3*3 2차원 배열에 존재하는 숫자들을 좌상단부터 우하단까지 이어지는 숫자 (1차원 배열, 엄밀히 말하면 String 형)로 표현하는 것이다
  • 위에서 변형한 String형태를 HashMap에 넣어 관리한다. HashMap <String, Integer>에서 String은 3x3을 1차원으로 바꾼 모습, Integer는 이 모습이 되기까지 몇 번의 움직임이 있었는지를 저장한다
  • bfs를 돌아가면서 ANS="123456780"와 같거나 큐가 빌 때까지 반복하면서 답을 확인한다

input

  for (int i=0; i<3; i++) {
      st=new StringTokenizer (br.readLine());
      for (int j=0; j<3; j++) {
          sb.append(st.nextToken());
      }
  }
  • 일반 2차원 맵을 입력 받는 것처럼 받지 않고 String형으로 입력을 받는다
  • StringBuilder sb를 선언하여 저장하였다

BFS, Queue

  • Queue처음 맵의 모습(String형으로 나타낸)을 넣고 시작한다
  • HashMap처음 맵의 모습 (init)과 0 (움직인 횟수)를 넣는다
  Queue<String> q=new ArrayDeque<>();
  q.add(init);
  map.put(init, 0);
  • Queue가 비거나, ANS="123456780"과 같아질 때까지 반복하면서 0의 위치를 움직이고 Queue와 HashMap에 넣는다
  • 1차원 형태에서 0이 있는 위치를 찾고 (zero), 2차원 배열에서 몇 행, 몇 열인지 구한다
  String pos=q.poll();
  int cnt=map.get(pos);
  int zero=pos.indexOf('0');
  int y=zero/3;
  int x=zero%3;
  
  if (pos.equals(ANS))
	return cnt;
  • 사방 탐색을 하면서 0이 움직일 위치를 찾아낸다
  • 0을 움직여서 나타낸 맵의 모습이 이미 HashMap에 있는 것이라면 (이미 방문한 적이 있다면) 탐색하지 않고, 그렇지 않다면 HashMap에 넣어주고, Queue에 넣어 다시 탐색한다
  for (int d=0; d<4; d++) {
      int ny=y+dy[d];
      int nx=x+dx[d];

      if (ny<0 || nx<0 || ny>=3 || nx>=3) continue;
      int nPos=ny*3+nx;
      char ch=pos.charAt(nPos);

      String next=pos.replace(ch, 'x');
      next=next.replace('0', ch);
      next=next.replace('x', '0');

      if (!map.containsKey(next)) {
          q.add(next);
          map.put(next, cnt+1);
      }
  }

Source Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static final int dy[]= {0,0,1,-1};
	static final int dx[]= {1,-1,0,0};

	static final String ANS="123456780";
	
	static Map<String, Integer> map=new HashMap<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader (new InputStreamReader (System.in));
		StringTokenizer st=null;
		StringBuilder sb=new StringBuilder();
		
		for (int i=0; i<3; i++) {
			st=new StringTokenizer (br.readLine());
			for (int j=0; j<3; j++) {
				sb.append(st.nextToken());
			}
		}

		System.out.println(bfs(sb.toString()));
	}
	
	private static int bfs (String init) {
		Queue<String> q=new ArrayDeque<>();
		q.add(init);
		map.put(init, 0);
		
		while (!q.isEmpty()) {
			String pos=q.poll();
			int cnt=map.get(pos);
			int zero=pos.indexOf('0');
			int y=zero/3;
			int x=zero%3;
			
			if (pos.equals(ANS))
				return cnt;
			
			for (int d=0; d<4; d++) {
				int ny=y+dy[d];
				int nx=x+dx[d];
				
				if (ny<0 || nx<0 || ny>=3 || nx>=3) continue;
				int nPos=ny*3+nx;
				char ch=pos.charAt(nPos);
				
				String next=pos.replace(ch, 'x');
				next=next.replace('0', ch);
				next=next.replace('x', '0');
				
				if (!map.containsKey(next)) {
					q.add(next);
					map.put(next, cnt+1);
				}
			}
		}
		return -1;
	}

}

2차원 배열을 1차원 형태로 나타내고, HashMap에 넣어 관리한다라는 아이디어를 생각하기가 힘들었다

profile
Backend 개발자 지망생

0개의 댓글