https://www.acmicpc.net/problem/14499

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지

www.acmicpc.net

문제 설명이 좀 어려운 문제 주사위 움직이는 칸의수는 무조건 1칸

그리고 주사위의 값의 변경의 규칙을 찾으면 쉽게 풀리는 문제네요

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {
	
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
	    ///크기 nxm 지도가 존재한다
		//지도의 오른쪽은 동쪽, 위쪼ㄱ은북쪽
		//주사위가 하나 놓여졋이다
		//지도의 좌표는  r,c로 나타나면 
		// r은 북쪽 c는 서쪽으로부터 떨어진갯수다
		//주사위는 지도 윗면이 1이고 동쪽을 바라보는 방향인 3인 상태로 놓여져잇으면
		//놓여져싱슨ㄴ 좌표는 x,y
		//가장 처음에 주사위에 모든 면에 0아더
		//지도의 각 칸에는 정수가 하나씩 쓰여져잇다.
		//주사위를 굴렷을떄, 이동한 칸에 쓰여 잇는 수가 0이면,
		//주사위의 바닥면에 쓰여잇는 수가 칸에 복사된다
		//0이 아닌 경우에는 칸에 쓰여잇는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여잇는 수
	    //0인된다
		//주사위는 지도 바깥으로 이동시킬수 없다
		//만약 바깥으로 이ㅏ동시키려고 하는 경우 명령을 무시해야하며 출력  x
		int []dice=new int[6];
		
		int n=scan.nextInt();
		int m=scan.nextInt();
		int x=scan.nextInt();
		int y=scan.nextInt();
		int k=scan.nextInt();
		
		int [][]maps=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				int r=scan.nextInt();
				maps[i][j]=r;
			}
			
		}
		
		for(int i=0;i<k;i++) {
			int command=scan.nextInt();
			int tmpx=0;
			int tmpy=0;
			if(command==1) {
				tmpx=x;
				tmpy=y+1;
			}else if(command==2) {
				tmpx=x;
				tmpy=y-1;
			}else if(command==3) {
				tmpx=x-1;
				tmpy=y;
			}else if(command==4) {
				tmpx=x+1;
				tmpy=y;
				
			}
			
			if(tmpx==-1||tmpy==-1||tmpx>=n||tmpy>=m) {
				continue;
			}
			
			if(command==1) {
				
				//동 3 ,5 0 0 0 7
				int tmp=dice[5];
				dice[5]=dice[2];
				dice[2]=dice[0];
				dice[0]=dice[3];
				dice[3]=tmp;
				
			}else if(command==2) {
				
				//서
				int tmp=dice[5];
				dice[5]=dice[3];
				dice[3]=dice[0];
				dice[0]=dice[2];
				dice[2]=tmp;
				
			}else if(command==3) {
				int tmp=dice[5];
				dice[5]=dice[1];
				dice[1]=dice[0];
				dice[0]=dice[4];
				dice[4]=tmp;
				
			}else if(command==4) {
	
				int tmp=dice[5];
				dice[5]=dice[4];
				dice[4]=dice[0];
				dice[0]=dice[1];
				dice[1]=tmp;
				
			}
			
			if(maps[tmpx][tmpy]!=0) {
				dice[5]=maps[tmpx][tmpy];
				maps[tmpx][tmpy]=0;
			}else {
				maps[tmpx][tmpy]=dice[5];
			}

			System.out.println(dice[0]); //0,0,0,0,0,3,
			x=tmpx;
			y=tmpy;

		}

	}
}

 

'알고리즘 공부' 카테고리의 다른 글

백준 집합의 표현  (0) 2023.12.12
백준 뱀과 사다리 게임  (1) 2023.12.12
백준 뱀  (0) 2023.12.05
백준 달력  (0) 2023.11.30
백준 신기한소수  (3) 2023.11.24

https://www.acmicpc.net/problem/3190

 

3190번: 뱀

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

아 흠 꼬리와 사과부분 처리가 조금 까다로웠던 문제네요 .. ㅠㅠ 

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {
	static class Snake{
		private int i;
		private int j;
		private int d;
		public Snake(int i,int j,int d) {
			this.i=i;
			this.j=j;
			this.d=d;
		}
		public void i(int i) {
			this.i=i;
		}
		public void j(int j) {
			this.j=j;
		}
		public void d(int d) {
			this.d=d;
		}
		public int i() {
			return i;
		}
		public int j() {
			return j;
		}
		public int d() {
			return d;
		}
	
	}
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int [][]maps=new int [n+1][n+1];
		boolean [][]bcheck=new boolean [n+1][n+1];
		//먼저 뱀이 몸길이를 늘려 머리를 다음칸에 위치시킨다
		//만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다
		//만약 이동한 칸에 사과가 잇다면 그칸에 잇던 사과가 없어지고 꼬리는 움직이지 않는다
		//만약에 이동칸에 사과가 없다면 몸길이를 줄여서 꼬리가 위치칸을 비워준다 즉 몸길이는 변하지 않는다
		//사과의 위치와 뱀의 이동 경로가 주어질 때 이게임이 몇초에 끝나는지  계산하여라 
		int k=scan.nextInt();
		
		
		
		for(int i=0;i<k;i++) {
			int x,y;
			x=scan.nextInt();
			y=scan.nextInt();
			maps[x][y]=1;
			
		}
		//0 오른쪽 1 아래 2 왼쪽 3 위 
		Snake snake=new Snake(1,1,0);
		Snake tail=new Snake(1,1,0);
		Deque<Snake>dq=new LinkedList<>();
		
		 dq.add(new Snake(1,1,0));
		
		bcheck[1][1]=true;
		//l 왼쪽 90도
		//d 오른쪽 90도
		int diri[]= {0,1,0,-1};
		int dirj[]= {1,0,-1,0};
		int l=scan.nextInt();
		int sec=0;
		int prev=0;
		int x=0;
		boolean bEnd=false;
		for(int i=0;i<l;i++) {
			int tmpx=scan.nextInt();
			char c=scan.next().charAt(0);
			
			 x=tmpx-prev;
			 prev=tmpx;
			 int dir=snake.d();
		     for(int j=0;j<x;j++) {
		    	 
				 int tmpDiri=diri[dir]+snake.i();
				 int tmpDirj=dirj[dir]+snake.j();
				
				 if(tmpDiri==0||tmpDirj==0||tmpDiri>=n+1||tmpDirj>=n+1) {
					 //벽
					 i=l+1;
					 sec++;
					 bEnd=true;
					 break;
				 }
				 
				 if( bcheck[tmpDiri][tmpDirj]==true) {
					 //뱀 몸
					 bEnd=true;
					 sec++;
					 i=l+1;
					 break;
				 }
				 
				 //apple?
				 if(maps[ tmpDiri ][ tmpDirj ]==1) {
					 maps[tmpDiri][tmpDirj]=0;//eating apple
				
				 }else {
					//not apple
					 Snake tmpTail=dq.getFirst();
					 dq.poll();
					 int taili=tmpTail.i();
					 int tailj=tmpTail.j();
					
					 bcheck[ taili ][ tailj ]=false;
					 
				 }
				 bcheck[tmpDiri][tmpDirj]=true;
				 dq.add(new Snake(tmpDiri,tmpDirj,0));
				 snake.i(tmpDiri);
				 snake.j(tmpDirj);
				 sec++;
		     }
		     
		     if(c=='L') {
		    	 dir=dir-1;
		    	 if(dir<0) {
		    		 dir=3;
		    	 }
		    	 
		     }else if(c=='D') {
		    	 dir=dir+1;
		    	 dir=dir%4;
		     }
		     snake.d(dir);
		   
			
		}
		 if(bEnd==false) {
			 while(true) {
					int dir=snake.d();
				    int tmpDiri=diri[dir]+snake.i();
				    int tmpDirj=dirj[dir]+snake.j();
				    if(tmpDiri==0||tmpDirj==0||tmpDiri>=n+1||tmpDirj>=n+1) {
						 //벽
						 sec++;
						 break;
					 }
				    if( bcheck[tmpDiri][tmpDirj]==true) {
						 //뱀 몸
						 sec++;
						 break;
					 }
				     Snake tmpTail=dq.peekFirst();
					 dq.pollFirst();
					 int taili=tmpTail.i();
					 int tailj=tmpTail.j();
					 bcheck[ taili ][ tailj ]=false;
				     bcheck[tmpDiri][tmpDirj]=true;
				     snake.i(tmpDiri);
					 snake.j(tmpDirj);
					  dq.add(snake);
					 sec++;
				}
		 }
		
		System.out.print(sec);
	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 뱀과 사다리 게임  (1) 2023.12.12
백준 주사위 굴리기  (1) 2023.12.11
백준 달력  (0) 2023.11.30
백준 신기한소수  (3) 2023.11.24
백준 상어 초등학교  (2) 2023.11.23

https://www.acmicpc.net/problem/20207

 

20207번: 달력

 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다.  여름이 거의 끝나가자 장

www.acmicpc.net

그리드 구현 문제인데.. 뭔가 dp문제에 조금 더 가까운 문제 같네요... 어렵네요

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {
	
	
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		//수현이는 일녀의 날짜가 1일 ~ 365일
		//
		//연소된 두일자에 각각 일정이 1개 이상있다면 이를 연속되었다고 표현하자
		//연속된 모든 일정은 하나의 직사각형에 포함되어야한다
		//연속된 모든 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.
		
		//달라ㅕㄱ은 다음과 같은 규칙을 따른다ㅣ.
		
		//일정은 시작날짜와 종료날짜를 포함한다
		//시작일이 가장 앞선 일정부터 차례대로 채워진다
		int n=scan.nextInt();
		HashMap<Integer ,Integer>maps=new HashMap<>();
		for(int i=1;i<=365;i++) {
			maps.put(i,0);
		}
		for(int i=0;i<n;i++) {
			int start=scan.nextInt();
			int end=scan.nextInt();
			for(int j=start;j<=end;j++) {
				maps.put(j,maps.get(j)+1);
			}
		}
		int h=0;
		int w=0;
		int mx=0;
		for(Integer key:maps.keySet()) {
			if(maps.get(key)>0) {
				w++;
				if(h<maps.get(key)) {
					h=maps.get(key);
				}
			}else {
				mx+=w*h;
				w=0;
				h=0;
			}
		}
		mx+=w*h;
		System.out.println(mx);
	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 주사위 굴리기  (1) 2023.12.11
백준 뱀  (0) 2023.12.05
백준 신기한소수  (3) 2023.11.24
백준 상어 초등학교  (2) 2023.11.23
백준 가장 큰 정사각형  (0) 2023.11.21

https://www.acmicpc.net/problem/2023

 

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수

www.acmicpc.net

딱히 어렵다기보단 소수구하는 방법이랑 문자열로 처리해야하는 부분만 잘 알고 있으면 쉽게 푸는 문제인듯하네요.

오히려 한 실버1정도 느낌인데 일단 골드5라고하니 애매하네요 

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {
	public static boolean [] bCheck=new boolean[10];
	public static void Prints(boolean [][]bCheck,int n,int m) {
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				int myindex=bCheck[i][j] ? 1 : 0;
				System.out.print(myindex);
			}
			System.out.println();
		}
	}
	//소수 찾기
	public static boolean checkingDecimal(long num) {
		if (num <= 1) {
	        return false;
	    }
	    for (long i = 2; i <= Math.sqrt(num); i++) {
	        if (num % i == 0) {
	            return false;
	        }
	    }
	    return true;
	}
	
	public static void backtracking(String k,int cnt,int limit) {
		long nk=Long.parseLong(k);
		if( checkingDecimal(nk)==false) {
			return ;
		}
		if(k.length() >= limit) {
			System.out.println(k);
			return ;
		}

		for(int i= 0 ;i<10;i++) {
			backtracking( k+Integer.toString(i), cnt+1, limit);
		}
	}
	
	
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		for(int i=0;i<10;i++) {
			backtracking(Integer.toString(i),0,n);
		}
	}
}

 

'알고리즘 공부' 카테고리의 다른 글

백준 뱀  (0) 2023.12.05
백준 달력  (0) 2023.11.30
백준 상어 초등학교  (2) 2023.11.23
백준 가장 큰 정사각형  (0) 2023.11.21
백준 치즈  (0) 2023.11.21

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호

www.acmicpc.net

골드5 문제인데 일반적인 골드5 구현문제들보다 난이도가 있네요 . 조건이 많아서 실수하기 좋은 문제인데 ;;; 게다가 이런문제는 시간도 오래 걸리기도 해서 골드 5보다는 조금 난이도가있지 않나 라고 생각이 듭니다;; 최소 골드4~3난이도 느낌이지만 일단 5라고 하니 5로 생각하죠 .. ㅎ 

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {
	
	public static void Prints(boolean [][]bCheck,int n,int m) {
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				int myindex=bCheck[i][j] ? 1 : 0;
				System.out.print(myindex);
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		//상어 초등학교에는 교실이 하나 있고 교실은 nxn 크기의 격자로 나타낼수 잇다
		//학교에는 n^2명 이다
		//모든 학생의 자리를 정하는 날이다
		//11, -> nn
		//선생이 학생의 순서를 정하고 => 학생이 좋아하는 학생 4명도 모두 조사햇다
		//이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자를 정하려한다.
		//한칸에는 학생 한명의 자리만 잇을수 잇고 r1-r2 + c1-c2 =1 을 만족하는 두칸이 r1,c1 r2,c2 를 인접한다
		
		//1 비어있는 칸중에서 좋아한느 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다
		//2.1을 만족하는 칸이 여러개이면, 인접한 카중에서 비어있는 칸이 가장많은 칸으로 자리를 정한다
		//3. 2를 만적하는 칸도 여러개이면, 행의 번호가 가장 작은 칸으로,. 그러한 칸도 여러개이면 열의 번호가 가장 작은 칸으로 자리르 정한다.
		//예를들어 n=3이고 3x3 
		//9명 학생 
		int n=scan.nextInt();
		int studentCount=n*n;
		int [][]students=new int[studentCount][5];
		int [][]studentsCheck=new int[studentCount+1][4];
		int [][]room=new int[n][n];
		int [][]happyCount=new int[n][n];
		boolean [][]bvisied=new boolean[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				bvisied[i][j]=false;
			}
		}
		
		for(int i=0;i<studentCount;i++) {
			for(int j=0;j<5;j++) {
				int tmp=scan.nextInt();
				students[i][j]=tmp;
				
			}
			
		}
		
		for(int i=0;i<studentCount;i++) {
			for(int j=1;j<5;j++) {
			studentsCheck[ students[i][0] ] [ j-1 ]=  students[i][j] ;
			}
		}
		
		int diri[]= {1,-1,0,0};
		int dirj[]= {0,0,1,-1};
		
		for(int k=0;k<studentCount;k++) {
			int maxLike=0;
			int maxBlank=0;
			int savei=-1;
			int savej=-1;
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
						int likeCount=0;
						int blankCount=0;
						if(bvisied[i][j]==true) {
							continue;
						}
					 
							for(int z=0;z<4;z++) {
								int tmpDiri=i+ diri[z];
								int tmpDirj=j+ dirj[z];
								
								//좋아하는 학생students[k][t];
								if(tmpDiri==-1||tmpDirj==-1||tmpDiri>=n||tmpDirj>=n) {
									continue;
								}
								
								 for(int t=1; t < 5;t++) { 
									 if(room[tmpDiri][tmpDirj]==students[k][t]) {
										 //인접한 좋아하는 학생
										 likeCount++;
									 }
								 }
								if(room[tmpDiri][tmpDirj]==0){
									//비어잇는칸
									blankCount++;
								}
							}
							
					    if(maxLike<likeCount) {
					    	 //비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
					    	savei=i;
							savej=j;
							maxLike=likeCount; //1 
							maxBlank=blankCount;
					    	 
					    }else if(maxLike==likeCount) {
					    	if(maxBlank<blankCount) {
					    		//1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
					    		maxBlank=blankCount;
					    		savei=i;
					    		savej=j;
					    	}else if(maxBlank==blankCount) {
					    		//2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
					    		
					    		if(savei>i) {
					    			savei=i;
					    		}else if(savei==i) {
					    			if(savej>j) {
					    				savej=j;
					    			}
					    		}
					    		
					    		if(savei==-1||savej==-1) {
					    			savei=i;
					    			savej=j;
					    		}
					    		
					    	}
					    	
					    }
					    
				}
			}
			//위치
			bvisied[savei][savej]=true;
			room[savei][savej]=students[k][0];
		}
		//만족도가 0 ->0
		//만족도가 1->1
		//만족도가 2>10
		//만족도가 3>100
		//만족도가 4>1000
		int happy=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				//System.out.print(room[i][j]+"->");
				int tmphappy=0;
				for(int z=0;z<4;z++) {
					int tmpdiri= i+diri[z];
					int tmpdirj= j+dirj[z];
					if(tmpdiri==-1||tmpdirj==-1||tmpdiri>=n||tmpdirj>=n) {
						continue;
					}
					
					for(int p=0;p<4;p++) {
						if(studentsCheck[ room[i][j] ][p]==room[tmpdiri][tmpdirj] ) {
							tmphappy++;
						}
					}
				}
				
				if(tmphappy==0) {
					happy+=0;
				}else if(tmphappy==1) {
					happy+=1;
				}
				else if(tmphappy==2) {
					happy+=10;
				}
				else if(tmphappy==3) {
					happy+=100;
				}
				else if(tmphappy==4) {
					happy+=1000;
				}
			}
		}
		System.out.println(happy);
	}
}

 
 

'알고리즘 공부' 카테고리의 다른 글

백준 달력  (0) 2023.11.30
백준 신기한소수  (3) 2023.11.24
백준 가장 큰 정사각형  (0) 2023.11.21
백준 치즈  (0) 2023.11.21
백준 주사위 (복습)  (1) 2023.11.21

https://www.acmicpc.net/problem/1915

 

1915번: 가장 큰 정사각형

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

www.acmicpc.net

자바로 풀었습니다. dp 문제이고 사실상 암기 문제? ㅋㅋ 가장 큰 정사각형을 찾는 공식입니다 . 뭔가 dp는 갈수록 공식문제 같네요.

dp[i][j]= Math.min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1])+1;

 

import java.util.*;

import java.lang.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan=new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int [][]maps=new int[n][m];
        scan.nextLine();
        for(int i=0;i<n;i++){
            String tmp=scan.nextLine();
            for(int j=0;j<tmp.length();j++){
                maps[i][j]=tmp.charAt(j)-'0';
            }
        }

        int [][]dp=new int[n][m];
        int gcnt=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(maps[i][j]==1){
                    if(i==0||j==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    }
                
                }
                gcnt=Math.max(gcnt,dp[i][j]);
            }
        }

        System.out.print(gcnt*gcnt);
    }
}

'알고리즘 공부' 카테고리의 다른 글

백준 신기한소수  (3) 2023.11.24
백준 상어 초등학교  (2) 2023.11.23
백준 치즈  (0) 2023.11.21
백준 주사위 (복습)  (1) 2023.11.21
백준 배 (복습)  (0) 2023.11.20

https://www.acmicpc.net/problem/2636

 

2636번: 치즈

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓

www.acmicpc.net

쉽네요 자바로 풀었습니다.

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {
	private int i;
	private int j;
	public Main() {
		
	}
	
	public Main(int i, int j) {
		this.i=i;
		this.j=j;
	}
	public int I() {
		return this.i;
	}
	public int J() {
		return this.j;
	}
	public void I(int i) {
		this.i=i;
	}
	public void J(int j) {
		this.j=j;
	}
	public static void Prints(boolean [][]bCheck,int n,int m) {
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				int myindex=bCheck[i][j] ? 1 : 0;
				System.out.print(myindex);
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int m=scan.nextInt();
		int [][]maps=new int[n][m];
		int [][]copymaps=new int[n][m];
		boolean [][]bVisisted=new boolean[n][m];
		boolean [][]copybVisisted=new boolean[n][m];
		Queue<Main> q=new LinkedList<>();
		int initcnt=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				int tmp=scan.nextInt();
				maps[i][j]=tmp;
				copymaps[i][j]=tmp;
				if(tmp==1) {
					bVisisted[i][j]=true;
					copybVisisted[i][j]=true;
					initcnt++;
				}else {
					bVisisted[i][j]=false;
					copybVisisted[i][j]=false;
					
					
				}
				
			}
		}
		
		
		int diri[]= {1,-1,0,0};
		int dirj[]= {0,0,1,-1};
		int mins=n*m;
		int tcnt=0;
		while(true) {
			q.add(new Main(0,0));
			boolean binit=false;
			while(!q.isEmpty()) {
				Main start=q.peek();
				q.poll();
				
				for(int i=0;i<4;i++) {
					int tmpDiri=start.I() +diri[i];
					int tmpDirj=start.J() +dirj[i];
					if(tmpDiri==-1||tmpDirj==-1||tmpDiri>=n||tmpDirj>=m) {
						continue;
					}
					if(bVisisted[tmpDiri][tmpDirj]==true) {
						if(maps[tmpDiri][tmpDirj]==1) {
							copymaps[tmpDiri][tmpDirj]=0;
							copybVisisted[tmpDiri][tmpDirj]=false;
							binit=true;
						}
						continue;
					}
					bVisisted[tmpDiri][tmpDirj]=true;
					q.add(new Main(tmpDiri,tmpDirj));
				}
				
			}
			
			int gcnt=0;
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					bVisisted[i][j]=copybVisisted[i][j];
					maps[i][j]=copymaps[i][j];
					if(maps[i][j]==1) {
						gcnt++;
					}
				}
			}
			
			if(binit==true) {
				tcnt++;
			}
			
			
			if(gcnt!=0) {
				mins=Math.min(gcnt, mins);
			}else {
				if(tcnt==1) {
					mins=initcnt;
				}
				break;
			}
			
		}
		System.out.println(tcnt);
		System.out.println(mins);
	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 상어 초등학교  (2) 2023.11.23
백준 가장 큰 정사각형  (0) 2023.11.21
백준 주사위 (복습)  (1) 2023.11.21
백준 배 (복습)  (0) 2023.11.20
백준 트리(복습)  (1) 2023.11.20

https://www.acmicpc.net/problem/1041

 

1041번: 주사위

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수

www.acmicpc.net

문제는 어렵진않는데 주사위의 위치를 잘 기억해서 최소3과 2의 값을 미리 구해야합니다. 자바로 풀었습니다.

import java.util.*;

import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;
public class Main {
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		long n=scan.nextLong();
		ArrayList<Long>dice=new ArrayList<>(); 
		for(int i=0;i<6;i++) {
			long tmp=scan.nextLong();
			dice.add(tmp);
		}

		long minthreesum=dice.get(0)+dice.get(1)+dice.get(2);//a b c
		 minthreesum=Math.min(minthreesum,dice.get(0)+dice.get(1)+dice.get(3));//a  b d
		 minthreesum=Math.min(minthreesum,dice.get(0)+dice.get(2)+dice.get(4));//a  d e
		 minthreesum=Math.min(minthreesum,dice.get(0)+dice.get(3)+dice.get(4));//a  c e
		 
		 minthreesum=Math.min(minthreesum,dice.get(5)+dice.get(1)+dice.get(2));//b  d f
		 minthreesum=Math.min(minthreesum,dice.get(5)+dice.get(1)+dice.get(3));//b  c f
		 minthreesum=Math.min(minthreesum,dice.get(5)+dice.get(2)+dice.get(4));//d  e  f
		 minthreesum=Math.min(minthreesum,dice.get(5)+dice.get(3)+dice.get(4));//c  e  f
		
		 long mintwosum=dice.get(0)+dice.get(1);// a b
		 
		 mintwosum=Math.min(mintwosum,dice.get(0)+dice.get(2)); //a c
		 mintwosum=Math.min(mintwosum,dice.get(0)+dice.get(3)); //a d
		 mintwosum=Math.min(mintwosum,dice.get(0)+dice.get(4)); //a e
		 
		 mintwosum=Math.min(mintwosum,dice.get(5)+dice.get(1)); //f b
		 mintwosum=Math.min(mintwosum,dice.get(5)+dice.get(2)); //f c
		 mintwosum=Math.min(mintwosum,dice.get(5)+dice.get(3)); //f d
		 mintwosum=Math.min(mintwosum,dice.get(5)+dice.get(4)); //f e
		 
		 mintwosum=Math.min(mintwosum,dice.get(1)+dice.get(3)); //b d
		 mintwosum=Math.min(mintwosum,dice.get(1)+dice.get(2)); //b c
		 mintwosum=Math.min(mintwosum,dice.get(4)+dice.get(3)); //e d
		 mintwosum=Math.min(mintwosum,dice.get(4)+dice.get(2)); //e c
		 
		
		Collections.sort(dice);
		//1,2,3,4,5,6
		long sum=0;
		if(n==1) {
			for(int i=0;i<5;i++) {
				sum+=dice.get(i);
			}
		}else {
			//윗꼭지점
			//3개
			sum=sum+( minthreesum )*4;
			
			//바닥 꼭지점
			sum=sum+( mintwosum )*4;
			
			long topsideline=8 * ( n-2 );
			long bottomline= 4 * ( n-2 );
			//윗변
			sum=sum+( mintwosum )*topsideline;
			//아랫변
			sum=sum+( dice.get(0) )*bottomline;
			
			//나머지
			
			long mod=(n-2)*(n-2)*5;
			sum=sum+( dice.get(0) )*mod;
			
			
		}
		System.out.println(sum);
	}
}

'알고리즘 공부' 카테고리의 다른 글

백준 가장 큰 정사각형  (0) 2023.11.21
백준 치즈  (0) 2023.11.21
백준 배 (복습)  (0) 2023.11.20
백준 트리(복습)  (1) 2023.11.20
백준 암호 만들기(복습)  (0) 2023.11.15

+ Recent posts