알고리즘 공부 #12 : BFS &DFS 활용3

백준 14226 : 이모티콘

import java.io.*;
import java.util.*;
class time{
	int time;
	int a;
	time(int a,int time){
		this.a=a;
		this.time=time;
	}
}
public class Main {
	static Scanner scan=new Scanner(System.in);
	static int[][] arr;
	static int s,n,x,y,max;
	static int[] visited;
	static int[] cnt;
	static Queue<time> q=new LinkedList<>();
	static StringBuilder sb=new StringBuilder();
    public static void main(String[] args)  {
    		
    	s=scan.nextInt();
    	visited=new int[1001];
    	  bfs();
      }
    public static void bfs() {
    	q.offer(new time(1,0));
    	while(!q.isEmpty()) {
    		time t=q.poll();
    		int time=t.time;
    		int a=t.a;
    		
    		if(a==s) {
    			System.out.println(time);
    		}
    		if(a*2<=1000&&visited[a*2]==0) {
    			visited[a*2]=1;
    			q.offer(new time(a*2,time+2));
    		}
    		if(a-1>2&&visited[a-1]==0) {
    			visited[a-1]=1;
    			q.offer(new time(a-1,time+1));
    			
    		}
    	}
    	
    	
    }
  
}

일단 생각나는대로 쓴 코드
어제 숨바꼭질3을 풀면서 가중치에 대한 개념을 해결하지 못했기때문에 어차피 틀렸겠지 했는데 코드 자체도 복사한후 계속 같은 값을 붙여넣기 할 수 있다는 사실을 간과했기때문에 틀렸다. (복사 붙여넣기를 합쳐서 +2초 과정으로함) 복사 / 붙여넣기 과정을 분리해서 생각할 필요가 있다.

import java.io.*;
import java.util.*;
class time{
	int time;
	int a;
	int clip;
	time(int a,int time,int clip){
		this.a=a;
		this.time=time;
		this.clip=clip;
	}
}
public class Main {
	static Scanner scan=new Scanner(System.in);
	static int[][] arr;
	static int s,n,x,y,max;
	static int[][] visited;
	static int[] cnt;
	static Queue<time> q=new LinkedList<>();
	static StringBuilder sb=new StringBuilder();
    public static void main(String[] args)  {
    		
    	s=scan.nextInt();
    	visited=new int[1001][1001];
    	  bfs();
      }
    public static void bfs() {
    	q.offer(new time(1,0,0));
    	while(!q.isEmpty()) {
    		time t=q.poll();
    		int time=t.time;
    		int a=t.a;
    		int c=t.clip;//클립보드
    		if(a==s) {
    			System.out.println(time);
    			return;
    		}
    		//지우기 -1
    		if(a-1>2&&visited[a-1][c]==0) {
    			visited[a-1][c]=1;
    			q.offer(new time(a-1,time+1,c));
    		}
    		//기존에 클립 보드에 있는 이모티콘을 붙여넣기 하는 경우
    		if(c+a<=1000&&visited[c+a][c]==0&&c!=0) {
    			visited[c+a][c]=1;
    			q.offer(new time(a+c,time+1,c));
    		}
    		
    		//지금 있는 이모티콘을 새로 복 붙 하는 경우
    		if(a*2<=1000&&visited[a*2][a*2]==0) {
    			visited[a*2][a*2]=1;
    			q.offer(new time(a*2,time+2,a));
    		}
    		
    	}
    	
    	
    }
  
}

https://www.acmicpc.net/board/view/30100
반례를 찾다가 이 질문글 보고 bfs에 대한 큰 깨달음을 얻다!

그래서 코드를 고쳐봤는데 안된다.(visited를 클립보드와 화면의 이모티콘수로 이중배열) 그래서 어제 해결못했던 가중치에 대해 찾아보았다. 가중치가 다른 그래프의 최단경로를 구하는 알고리즘은 다익스트라이다. 어제 풀었던 그래프의 경우 가중치가 0과 1이었기때문에 0-1 bfs로 풀 수 있었고 내가 쓴 코드는 가중치가 2 1 이기때문에 2를 1로 바꿀 필요가 있었다. 복붙을 분리했다.

[정답코드]

import java.io.*;
import java.util.*;
class time{
	int time;
	int a;
	int clip;
	time(int a,int time,int clip){
		this.a=a;
		this.time=time;
		this.clip=clip;
	}
}
public class Main {
	static Scanner scan=new Scanner(System.in);
	static int[][] arr;
	static int s,n,x,y,max;
	static int[][] visited;
	static int[] cnt;
	static Queue<time> q=new LinkedList<>();
	static StringBuilder sb=new StringBuilder();
    public static void main(String[] args)  {
    		
    	s=scan.nextInt();
    	visited=new int[1001][1001];
    	  bfs();
      }
    public static void bfs() {
    	q.offer(new time(1,0,0));
    	visited[1][0]=1;
    	while(!q.isEmpty()) {
    		time t=q.poll();
    		int time=t.time;
    		int a=t.a;
    		int c=t.clip;//클립보드
    		
    		if(a==s) {
    			System.out.println(time);
    			break;
    		}
    		
    		//복사
    		if(a!=c&&visited[a][a]==0) {
    			q.offer(new time(a,time+1,a));
    			visited[a][a]=1;
    		}

    		//지우기 -1
    		if(a-1>2&&visited[a-1][c]==0) {
    			visited[a-1][c]=1;
    			q.offer(new time(a-1,time+1,c));
    		}
    		
    		//붙여넣기
    		if(c+a<=1000&&visited[c+a][c]==0&&c!=0) {
    			visited[c+a][c]=1;
    			q.offer(new time(a+c,time+1,c));
    		}
    		
    	}
    	
    	
    }
  
}

백준 3055 : 탈출

import java.io.*;
import java.util.*;
class xy{
	int x;
	int y;
	xy(int x, int y){
		this.x=x;
		this.y=y;
	}
}
public class Main {
	static Scanner scan=new Scanner(System.in);
	static char[][] arr;
	static int r,c,max;
	static int[][] visited,dist_water,dist_go;
	static int[] dx= {1,0,0,-1};
	static int[] dy= {0,-1,1,0};
	static StringBuilder sb=new StringBuilder();
    public static void main(String[] args)  {
    	r=scan.nextInt();	//ㄱㅏ로
    	c=scan.nextInt();	//세로
    	arr=new char[r][c];
    	visited=new int[r][c];
    	dist_water=new int[r][c];
    	dist_go=new int [r][c];
    	for(int i=0;i<r;i++) {
    		String str=scan.next();
    		for(int j=0;j<c;j++) {
    			arr[i][j]=str.charAt(j);
    		}
    	}
    	bfs_water();
    	bfs_go();
    	
    	for(int i=0;i<r;i++) {
    		for(int j=0;j<c;j++) {
    			if(arr[i][j]=='D') {
    				if(dist_go[i][j]==-1) {
    					System.out.println("KAKTUS");
    				}
    				else {
    					System.out.println(dist_go[i][j]);
    				}
    			}
    		}
    	}

	
    }
    //물의 시간을 dist_water에 저장하는 과정
	public static void bfs_water(){
		Queue<xy>q=new LinkedList<>();
		//물의 위치를 모두 q에 넣어서 탐색 시작
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				dist_water[i][j]=-1;
				if(arr[i][j]=='*') {
					q.offer(new xy(i,j));
					dist_water[i][j]=0;
					visited[i][j]=1;
				}
			}
		}
		while(!q.isEmpty()) {
			xy xy=q.poll();
			int x=xy.x;
			int y=xy.y;
			for(int k=0;k<4;k++) {
				int nextx=x+dx[k];
				int nexty=y+dy[k];
				if(nextx<0||nexty<0||nextx>=r||nexty>=c)continue;
				if(arr[nextx][nexty]!='.')continue;
				if(visited[nextx][nexty]==0) {
					q.offer(new xy(nextx,nexty));
					visited[nextx][nexty]=1;
					dist_water[nextx][nexty]=dist_water[x][y]+1;
				}
			}
		}
	}   
    public static void bfs_go() {
    	Queue<xy>q=new LinkedList<>();
    	for(int i=0;i<r;i++) {
    		for(int j=0;j<c;j++) {
    			dist_go[i][j]=-1;
    			visited[i][j]=0;
    			if(arr[i][j]=='S') {
    				q.offer(new xy(i,j));
    				dist_go[i][j]=0;
    				visited[i][j]=1;
    			}
    		}
    	}
    	while(!q.isEmpty()) {
    		xy xy=q.poll();
    		int x=xy.x;
    		int y=xy.y;
    		for(int k=0;k<4;k++) {
    			int nextx=x+dx[k];
    			int nexty=y+dy[k];
				if(nextx<0||nexty<0||nextx>=r||nexty>=c)continue;
				if(arr[nextx][nexty]!='.'&&arr[nextx][nexty]!='D')continue;
				if(dist_water[nextx][nexty]!=-1&&dist_water[nextx][nexty]<=dist_go[x][y]+1) continue;
				if(visited[nextx][nexty]==1)continue;
				q.offer(new xy(nextx,nexty));
				visited[nextx][nexty]=1;
				dist_go[nextx][nexty]=dist_go[x][y]+1;
    		}
    	}
    	
    	
    }
  
}

bfs를 두번 사용해야해서 복잡하고 헷갈리니까 다시 풀어보기