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));
}
}
}
}
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를 두번 사용해야해서 복잡하고 헷갈리니까 다시 풀어보기