[알고리즘] 퍼즐 (백준 1525번)

1525번: 퍼즐

 비트마스킹 문제를 찾고 있었는데 비트마스킹으로 풀기엔 시간이 너무 오래걸려서 그냥 배열을 이용해서 풀었다.

BFS를 이용해야 하는 문제다.

 

Solution

 우선 고려해야할 것은 1차원 배열의 index와 2차원 배열의 row, column을 왔다갔다 해야되는 것이다. 여기서 핵심은 visited, 즉 방문 처리를 무엇으로 할 것이냐 인데 난 int형 배열을 이용해서 처리했다. 문자열을 사용하는 사람도 있는데 문자열로도 성공은 하지만 메모리 사용량 측면에선 int형 배열이 훨씬 효율적이다.

 

1. 전역 변수

	static HashSet<Position> visited = new HashSet<>();
	static int end[] = {8, 0, 1, 2, 3, 4, 5, 6, 7};

	//최종 목적지
	static Position finish = new Position(end, 0);

•  visited : 방문여부를 처리해주는 set
• end : 최종 결과의 모습
• finish : 최종 결과 객체

 

2. swap 함수

//2차원 배열 -> 1차원 배열 index로
	static int toOneDimension(int x, int y)
	{
		return x * 3 + y;
	}

 2차원 배열의 row, column을 1차원 배열 index로 변환한다.

 

3. getRow, getColumn 함수

	static int getRow(int index)
	{
		return index / 3;
	}

	static int getColumn(int index)
	{
		return index % 3;
	}

 1차원 배열의 index를 2차원 배열의 row, column을 변환한다.

 

4. swap 함수

	static void swap(int[] pos, int next_index)
	{
		//next 위치에 해당하는 번호와 0의 위치를 swap
		for(int i = 0;i < 9;i++)
		{
			if(pos[i] == next_index)
			{
				pos[i] = pos[0];
				pos[0] = next_index;
				return;
			}
		}
	}

 0과 next_index에 있는 번호의 위치를 바꾼다.

 

5. Position 클래스

	static class Position{
		int[] pos;//i의 현재 위치 비트마스크들
		int count = 0;

		public Position(int[] pos, int count) {
			this.pos = pos;
			this.count = count;
		}

		@Override
		public boolean equals(Object obj) {
			return Arrays.equals(pos, ((Position)obj).pos);
		}

		@Override
		public int hashCode() {
			return Arrays.hashCode(pos);
		}
	}

• pos[] : 숫자들의 현재 위치를 나타낸다.
• count : 움직인 횟수를 나타낸다.
• hashCode() : HashSet에서 사용하기 위해서 pos 배열의 hashcode를 반환한디.
• equals() : 배열끼리의 비교 결과를 반환한다.

 

6. BFS 함수

	static int bfs(int[] init)
	{
		Queue<Position> queue = new LinkedList<>();
		queue.offer(new Position(init, 0));
		visited.add(queue.peek());

		int x[] = {-1, 1, 0, 0};//상하좌우
		int y[] = {0, 0, -1, 1};

		while(!queue.isEmpty())
		{
			Position now = queue.poll();
			int current_index = now.pos[0];

			//종료
			if(now.equals(finish))
				return now.count;

			int r = getRow(current_index);
			int c = getColumn(current_index);

			//상하좌우
			for(int i = 0;i < 4;i++)
			{
				int next_r = r + x[i];
				int next_c = c + y[i];

				if(0 <= next_r && next_r < 3 && 0 <= next_c && next_c < 3)
				{
					int next_index = toOneDimension(next_r, next_c);

					swap(now.pos, next_index);

					if(!visited.contains(now))
					{
						Position next_pos = new Position(now.pos.clone(), now.count + 1);
						visited.add(next_pos);
						queue.offer(next_pos);
					}

					swap(now.pos, current_index);
				}
			}
		}
		return -1;
	}

 현재 0번의 위치를 기준으로 상하좌우의 이동할 수 있는 곳들로 이동시킨 후 queue에 넣는다. 상하좌우 반복문을 돌 때마다 원본 배열의 위치는 다시 swap해서 원래대로 바꿔놔야한다.

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static HashSet<Position> visited = new HashSet<>();
	static int end[] = {8, 0, 1, 2, 3, 4, 5, 6, 7};
	
	//최종 목적지
	static Position finish = new Position(end, 0);

	public static void solution() throws Exception
	{
		//초기 상태 (input)
		int init[] = new int[9];
		
		for(int i = 0;i < 3;i++)
		{
			StringTokenizer strtok = new StringTokenizer(br.readLine());
			for(int j = 0;j < 3;j++)
			{
				int num = Integer.parseInt(strtok.nextToken());
				int pos = toOneDimension(i, j);
				init[num] = pos;
			}
		}

		bw.write(bfs(init)+"");

	}

	static int bfs(int[] init)
	{
		Queue<Position> queue = new LinkedList<>();
		queue.offer(new Position(init, 0));
		visited.add(queue.peek());

		int x[] = {-1, 1, 0, 0};//상하좌우
		int y[] = {0, 0, -1, 1};

		while(!queue.isEmpty())
		{
			Position now = queue.poll();
			int current_index = now.pos[0];

			//종료
			if(now.equals(finish))
				return now.count;

			int r = getRow(current_index);
			int c = getColumn(current_index);

			//상하좌우
			for(int i = 0;i < 4;i++)
			{
				int next_r = r + x[i];
				int next_c = c + y[i];

				if(0 <= next_r && next_r < 3 && 0 <= next_c && next_c < 3)
				{
					int next_index = toOneDimension(next_r, next_c);

					swap(now.pos, next_index);

					if(!visited.contains(now))
					{
						Position next_pos = new Position(now.pos.clone(), now.count + 1);
						visited.add(next_pos);
						queue.offer(next_pos);
					}

					swap(now.pos, current_index);
				}
			}
		}
		return -1;
	}

	//2차원 배열 -> 1차원 배열 index로
	static int toOneDimension(int x, int y)
	{
		return x * 3 + y;
	}

	static int getRow(int index)
	{
		return index / 3;
	}

	static int getColumn(int index)
	{
		return index % 3;
	}


	static void swap(int[] pos, int next_index)
	{
		//next 위치에 해당하는 번호와 0의 위치를 swap
		for(int i = 0;i < 9;i++)
		{
			if(pos[i] == next_index)
			{
				pos[i] = pos[0];
				pos[0] = next_index;
				return;
			}
		}
	}

	static class Position{
		int[] pos;//i의 현재 위치 비트마스크들
		int count = 0;

		public Position(int[] pos, int count) {
			this.pos = pos;
			this.count = count;
		}

		@Override
		public boolean equals(Object obj) {
			return Arrays.equals(pos, ((Position)obj).pos);
		}

		@Override
		public int hashCode() {
			return Arrays.hashCode(pos);
		}
	}

	public static void main(String[] args) {
		try
		{
			solution();
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}