REAL 복습 (4)

4/3일자, 3/31일자

1. 신입사원 - 백준 1946 (Greedy)

   :timer_clock: 10:44 - 11:01 (17min)

   package greeedy;
      
   import java.util.*;
   public class beak_신입사원_re {
      
   	//10:44 - 11:01
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		int n = sc.nextInt();
      		
   		for(int i=0; i<n; i++) {
   			int m = sc.nextInt();
   			int arr[][] = new int[m][2];
      			
   			for(int j=0; j<m; j++) {
   				arr[j][0] = sc.nextInt();
   				arr[j][1] = sc.nextInt();
   			}
      			
   			Arrays.sort(arr, new Comparator<int[]>() {
   				@Override
   				public int compare(int a[], int b[]) {
   					return a[0]-b[0];
   				}
   			});
      			
   			int answer = 1;
   			int min = arr[0][1];
      			
   			for(int j=1; j<m; j++) {
   				if(min > arr[j][1]) {
   					min = arr[j][1];
   					answer++;
   				}
   			}
      			
   			System.out.println(answer);
   		}
      		
   	}
   }
      
   

2. 이동하기 - 백준 11048 (Greedy)

   ⏲ 11:08 - 11:28 (20min)

   package DP;
      
   import java.util.*;
      
   public class beak_이동하기_re {
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		int n = sc.nextInt();
   		int m = sc.nextInt();
      		
   		int arr[][] = new int[n+1][m+1];
      		
   		for(int i=1; i<=n; i++) {
   			for(int j=1; j<=m; j++)
   				arr[i][j] = sc.nextInt();
   		}
      		
   		for(int i=1; i<=n; i++) {
   			for(int j=1; j<=m; j++) {
   				if(i == 1)
   					arr[i][j] += arr[i][j-1];
      				
   				else if(j==1)
   					arr[i][j] += arr[i-1][j];
      				
   				else
   					arr[i][j] += Math.max(Math.max(arr[i-1][j-1], arr[i-1][j]),arr[i][j-1]);
   			}
   		}
      
   		int answer = Integer.MIN_VALUE;
   		for(int i=1; i<=m; i++) {
   			answer = Math.max(answer, arr[n][i]);
   		}
      		
   		System.out.println(answer);
   	}
   }
      
   

   • 오바잖아.. 이십분…
   • if, else if, else 일때의 조건을 확실히 걸어주어야 겹치지 않음!
   • 또 n+1 ,m+1로 할거면 기준 정확하게 잡아주기!

3. 보물섬 - 백준 2589 (BFS)

   ⏲ 11:38 - 12:05 (28min)

   package Dfs_Bfs;
      
   import java.util.*;
   public class beak_보물섬_re {
   	static char arr[][];
   	static int n;
   	static int m;
      	
   	static class Pos{
   		int x;
   		int y;
   		int cnt;
   		Pos(int x, int y, int cnt){
   			this.x = x;
   			this.y = y;
   			this.cnt = cnt;
   		}
   	}
      	
   	static int dx[] = {0,0,1,-1};
   	static int dy[] = {1,-1,0,0};
      	
   	public static int bfs(int x, int y) {
   		int an=0;
   		boolean visited[][] = new boolean[n][m];
      		
   		Queue<Pos> qu = new LinkedList<>();
   		qu.add(new Pos(x,y,0));
   		visited[x][y] = true;
      		
   		while(!qu.isEmpty()) {
   			Pos p = qu.poll();
      			
   			for(int i=0; i<4; i++) {
   				int nx = p.x + dx[i];
   				int ny = p.y + dy[i];
      				
   				if(nx>=0&&nx<n&&ny>=0&&ny<m&&arr[nx][ny] == 'L' &&!visited[nx][ny]) {
   					visited[nx][ny] = true;
   					qu.add(new Pos(nx,ny,p.cnt+1));
   					an = Math.max(an, p.cnt+1);
   				}
   			}
      			
   		}
      		
   		return an;
   	}
      	
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		n = sc.nextInt();
   		m = sc.nextInt();
      		
   		arr = new char[n][m];
      		
   		sc.nextLine();
      		
   		for(int i=0; i<n; i++) {
   			String a = sc.nextLine();
   			for(int j=0; j<m; j++) {
   				arr[i][j] = a.charAt(j);
   			}
   		}
   		int answer = 0;
      		
   		for(int i=0; i<n; i++) {
   			for(int j=0; j<m; j++) {
   				if(arr[i][j] == 'L') {
   					int temp = bfs(i,j);
   					answer = Math.max(answer, temp);
   				}
   			}
   		}
      		
   		System.out.println(answer);
      		
   	}
   }
   

   • 이 문제의 힌트는!!!!!!!!!!! ‘L’인 시작점 전부를 bfs를 타본다는 것이다!

4. 케빈 베이컨의 6단계 법칙 - 백준 1389 (BFS)

   ⏲ 12:28 - 12:08 (40min)

   package Dfs_Bfs;
      
   import java.util.*;
      
   public class beak_케빈베이컨의법칙_re {
      	
   	public static void main(String[] args) {
   		Scanner sc = new Scanner(System.in);
      		
   		int n = sc.nextInt();
      		
   		int m = sc.nextInt();
   		int arr[][] = new int[m][2];
      		
   		sc.nextLine();
      		
   		for(int i=0; i<m; i++) {
   			arr[i][0] = sc.nextInt();
   			arr[i][1] = sc.nextInt();
   		}
      		
   		int answer []= new int[n+1];
      		
   		for(int i=1; i<=n; i++) {
   			Queue<Integer> qu = new LinkedList<>();
   			boolean v[] = new boolean[n+1];
   			int sum[] = new int[n+1];
      			
   			qu.add(i);
   			v[i] = true;
      			
   			while(!qu.isEmpty()) {
   				int x = qu.poll();
      				
   				for(int j=0; j<m; j++) {
   					if(arr[j][0] == x && !v[arr[j][1]]) {
   						//걔까지는 갈수있으니까
   						qu.add(arr[j][1]);
   						v[arr[j][1]] = true;
   						sum[arr[j][1]] += sum[arr[j][0]] +1;
   					}
      					
   					if(arr[j][1] == x && !v[arr[j][0]]) {
   						//걔까지는 갈수있으니까
   						qu.add(arr[j][0]);
   						v[arr[j][0]] = true;
   						sum[arr[j][0]] += sum[arr[j][1]] +1;
   					}
   				}
      				
   			}//while
      			
   			for(int k:sum) {
   				answer[i] += k;
   			}	
   		}
      		
   		int idx = 0;
   		int real = answer[n];
   		for(int i=n-1; i>=1; i--) {
   			if(real>=answer[i]) {
   				real = answer[i];
   				idx = i;
   			}
   		}
      	
   		System.out.println(idx);
   	}
   }
   

   • 아 어렵다..
   • 힌트!!!!
   • 1부터 n까지 돌리면서 qu와 sum[], v[]를 매번 생성한다**
   • qu.add(x)가지고 들어갔으면 1. 안방문했던 곳이며 2.x 의 친구라면
   • x가 가지는 위치 +1을 해주고, true를 해주면서 들어간다
   • 이 포인트만 기억하면 금방 풀 수 있다!