[백준] 퍼즐

[hye-on]

🔗 퍼즐

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

#include <iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;

#define INF 2000000000
//1:55 2:38
//bfs, 완탐 , 방문 여부는 map으로

string pTos(vector<vector<int>>&p){
    string ret="";
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            ret+=to_string(p[i][j]);
        }
    }
    return ret;
}


vector<vector<int>>p(3,vector<int>(3,0));
map<string,bool>visit;

queue<pair<pair<int,int>,pair<string,int>>>q; //y,x, 배열 상태, 이동 횟수
int answer=INF;
string answerMap="123456780";

bool OOB(int y,int x){
    if(y>=3 || y<0 || x>=3 ||x<0)
        return true;
    return false;
}
void bfs(){

    int dy[] = {0,1,0,-1};
    int dx[] = {1,0,-1,0};
    
    while(!q.empty()){
       
        int curY = q.front().first.first;
        int curX = q.front().first.second;

        string curMap = q.front().second.first;
        int dist = q.front().second.second;
        q.pop();
        
        if(curMap == answerMap){
            answer = dist;
            break;
        }

        for(int i=0;i<4;i++){
            int ny = curY + dy[i];
            int nx = curX + dx[i];
           
            if(OOB(ny,nx))
                continue;
           
            //1차원 좌표로 바꾸기
            int cur_pos = curY*3 + curX;
            int n_pos = ny*3 + nx;

            //이동하기
            string t = curMap;
            t[cur_pos] =t[n_pos];
            t[n_pos] = '0';
         
            
            //이미 방문한 적이 있으면
            if(visit.find(t)!=visit.end())
                continue;
             visit[t]=true;
            q.push({{ny,nx},{t,dist+1}});
            
        }
    }
}

int main() {

    
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin>>p[i][j];
            if(p[i][j]==0){
                q.push({{i,j},{"",0}});
            }
        }
    }
    q.front().second.first = pTos(p);
    bfs();
    
    if(answer==INF)
        answer=-1;
    cout<<answer;
    
    return 0;
}

코멘트

- string으로 경로를 저장했습니다!

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

import java.io.*;
import java.util.*;

// 10:50 시작! 
public class Main {
       /**
         * 완탐(언제 끝날지 모름 -> 즉, 불가능한 경우를 찾기 어려움)
         */
        static String answer = "123456780";
        static Set<String> set = new HashSet<>();
        static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	public static void main(String[] args) throws Exception {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st;
	    
	    String table = "";
	    for(int i = 0; i < 3; ++i) {
	        st = new StringTokenizer(bf.readLine());
	        for(int j = 0; j < 3; ++j) {
	            table += Integer.parseInt(st.nextToken());
	        }
	    }

	    System.out.println(bfs(table));
        }
	
	public static int bfs(String start) {
	    Queue<Node> q = new LinkedList<>();
	    set.add(start);
	    q.offer(new Node(start, 0));
	    
	    while(!q.isEmpty()) {
	        Node cur = q.poll();
	        String table = cur.table;
	        
	        int idx = table.indexOf('0');
	        int zx = idx / 3;
	        int zy = idx % 3;
	        
	        if(table.equals(answer)) return cur.move;
	        
	        for(int d = 0; d < 4; ++d) {
	            int x = zx + dx[d];
	            int y = zy + dy[d];
	            
	            if(x < 0 || x >= 3 || y < 0 || y >= 3) continue;
	           
	            int numIdx = x * 3 + y;
	            char num = table.charAt(numIdx);
                    String next = table.replace(num, 'z');
                    next = next.replace('0', num);
                    next = next.replace('z', '0');
                
                    if(!set.contains(next)) {
                        set.add(next);
                        q.offer(new Node(next, cur.move + 1));
                    }
	      }
	    }
	    
	    return -1;
	}
	
	public static class Node {
	    String table;
	    int move;
	    
	    public Node(String table, int move) {
	        this.table = table;
	        this.move = move;
	    }
	}
}

코멘트

- BFS할 때마다 배열 상태를 넘겨줘야 하는데, 배열을 쓰면 메모리를 너무 많이 차지해서 String을 사용했습니다:)