[BOJ] #2589 보물섬, #7562 나이트의 이동, #11559 Puyo Puyo (JAVA)

네,, 저 자바로 코테 언어 변경 했슴니다 ,,

매주 3문제씩 문제 풀고 블로그에 업로드 하기로도 했슴니다,, 

#2589 보물섬

문제 이해

0. 육지와 육지에서 가장 멀리 떨어진 거리에서 움직이는 시간을 구해야 한다.

1. 1칸당 1초이고 방문했던 곳을 방문해서는 안된다.

2. 가장 멀리 떨어진 점이고 그 점에서는 최단거리여야 한다.

 

 

해결 방법 고안

1. 최단 경로를 구해야 하므로 BFS를 사용하기로 생각했다.

2. 두 점이 나와있지 않기에 한 점 (육지)를 잡아서 그 점에서 부터 멀리 떨어진 것을 BFS로 return 해준다.

3. 그 점 들 중에서 가장 멀리 떨어진 것을 구해야 하므로 Math.max을 사용했다.

4. 즉, 육지인 한점 -> bfs 사용해서 가장 최단 거리이면서 가장 멀리 떨어진 시간 return

5. 시간들 중에서도 가장 큰 시간 출력

 

코드 설명

import java.io.*;
import java.util.*;
public class Main {
	private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer tokens;

	static char map[][];
	private static boolean visited[][];
	private static int deltas[][] = {{0,1},{1,0}, {-1,0}, {0,-1}};
	private static int max_value=Integer.MIN_VALUE;
	
	private static int c, r, cnt, dx, dy;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		tokens = new StringTokenizer(input.readLine());
		r = Integer.parseInt(tokens.nextToken());
		c = Integer.parseInt(tokens.nextToken());
		
		map = new char[r][c];
		for(int i=0; i<r; i++) {
			tokens = new StringTokenizer(input.readLine());
			String temp=tokens.nextToken();
			for(int j=0; j<c; j++) {
				map[i][j]=temp.charAt(j);
			}
		}
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				if(map[i][j] =='L') {
					max_value = Math.max(max_value, bfs(i,j,0));
				}
			}
		}
		System.out.println(max_value);
	}

	private static int bfs(int x, int y, int cnt) {
		Queue<int[]>que =new LinkedList<>();
		visited =new boolean[r][c];
		que.offer(new int[] {x,y,cnt});
        visited[x][y]=true;
		int max_distance=0;
		while(!que.isEmpty()) {
			int t[] = que.poll();
			x = t[0];
			y = t[1];
			cnt = t[2];
			
			max_distance = Math.max(max_distance, cnt);
			
			for(int d[]: deltas) {
				int nx = x+d[0];
				int ny = y+d[1];
				
				if(nx>=0 && nx<r && ny>=0 && ny<c) {
					if(!visited[nx][ny]) {
						if(map[nx][ny]=='L') {
							que.offer(new int [] {nx, ny, cnt+1});
							visited[nx][ny]=true;
						}
						
					}
				}
			}
		}
		return max_distance; //현재 점 중에 가장 큰 값
	}
}

 

큰거 중에 큰거를 구한다고 생각하니 1-2시간 이내로 구현할 수 있었다!

 

#7562 나이트의 이동

문제 이해

0. 현재 위치에서 이동하려고 하는 칸까지의 최단 거리를 구해야 한다.

1. 이동 할 수 있는 칸은 총 8개로 정해져있다. {{-1,-2}, {-2,-1}, {-2,1}, {-1,2}, {1,-2}, {2,-1}, {1,2},{2,1}}

 

해결 방법 고안

0. 최단 시간이므로 BFS 풀어야겠다고 생각

1. 현재 위치와 목표 위치가 같으면 바로 return;

코드 설명

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

public class Boj7562 {
	private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer tokens;
	private static StringBuilder output = new StringBuilder();
	private static int map [][];
	private static int deltas[][] = {{-1,-2}, {-2,-1}, {-2,1}, {-1,2}, {1,-2}, {2,-1}, {1,2},{2,1}};
	
	private static int t,l,x,y,dx,dy;
	private static int min_value = Integer.MAX_VALUE;
	private static boolean visited[][];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		t =Integer.parseInt(input.readLine());
		for(int tc=0; tc<t; tc++) {
			l = Integer.parseInt(input.readLine()); 
			map = new int[l][l];
			visited = new boolean [l][l];
			tokens = new StringTokenizer(input.readLine());
			x =Integer.parseInt(tokens.nextToken());
			y =Integer.parseInt(tokens.nextToken());
			tokens = new StringTokenizer(input.readLine());
			dx =Integer.parseInt(tokens.nextToken());
			dy =Integer.parseInt(tokens.nextToken());
			min_value=bfs(x,y,0);
			output.append(min_value).append('\n');
		}
		System.out.println(output);
	}
	private static int bfs(int x, int y, int cnt) {
		
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[]{x, y, 0}); //현재 위치랑 cnt를 배열로 넣어놓기

		while(!que.isEmpty()) { 
			int locate[]=que.poll();
			x = locate[0];
			y = locate[1];
			cnt = locate[2];
			
			if(x==dx && y==dy) { //중단 기준은 만날 때
				return cnt;
			}
			
			for(int[] d: deltas) {
				int nx = x+d[0];
				int ny = y+d[1];
				if(nx>=0 && nx<l && ny>=0 && ny<l) {
					if(map[nx][ny]==0) {
						que.offer(new int[] {nx,ny, cnt+1});
						map[nx][ny]=1;
					}
				}
			}
		}
		return -1;
	}
}

 

que에 한번에 cnt까지 매개변수로 저장해서 두 좌표가 일치한다면 그때 cnt를 return하면 된다.

같은 시점에 que에 들어오는 거는 cnt가 같기 때문에 고려하지 않아도 되어서 최단 시간을 찾을 수 있는 것이다.

Queue에 들어오는 타입을 int 배열로 설정하였으면 값을 넣을 때 new int[]{}로 offer 혹은 add하면 된다.

 

# 11559 Puyo Puyo

문제 이해

0. '.'이 아니면 뿌요이다.

1. 뿌요가 상하좌우로 4개 이상 모이면 '.'이 된다.

2. 터지고 내려올 때 연쇄가 +1 추가된다. 

해결 방법 고안

1. 뿌요가 있다면 아래로 떨어지는 함수 fall()를 구현한다.

2. 상하좌우로 4개 이상 모이면 터지는 BFS를 구현한다.

3. 터지고 내려올 수 있다면 count에 +1를 추가한다.

코드 설명

BFS 함수

- 좌표를 담을 que와 4개 이상 뿌요가 있는 좌표를 담을 location queue가 필요하다.

- count가 4 이상이면 location에 있는 뿌요의 위치를 '.'로 변경한다.

static boolean bfs(int x, int y) {
    Queue<int[]> que = new LinkedList<>();
    Queue<int[]> location = new LinkedList<>();

    char color = map[x][y];
    que.offer(new int[] {x, y});
    location.offer(new int[] {x, y});
    visited[x][y] = true;
    int count = 0;
    while (!que.isEmpty()) {
        int[] t = que.poll();
        int dx = t[0];
        int dy = t[1];
        count++;

        for (int[] d : deltas) {
            int nx = dx + d[0];
            int ny = dy + d[1];

            if (nx >= 0 && nx < 12 && ny >= 0 && ny < 6 && !visited[nx][ny] && map[nx][ny] == color) {
                que.offer(new int[] {nx, ny});
                location.offer(new int[] {nx, ny});
                visited[nx][ny] = true;
            }
        }
    }

    if (count >= 4) {
        while (!location.isEmpty()) {
            int[] p = location.poll();
            map[p[0]][p[1]] = '.';
        }
        return true;
    }
    return false;
}

 

fall 함수

- 아래서 위를 기준으로 탐색 (3중 반복문)

- 예를 들어 열을 0이면 행을 11,10,9,8.. 위로 올라가면서 '.'이 아닌 것을 탐색

- 열에 뿌요가 나오지 않으면 열을 +1로 넘어감

- 열에 뿌요가 나온다면 맨 아래에 뿌요를 넣어두고, 뿌요가 있었던 곳에는 '.'를 넣는다.

    static void fall() {
    	//아래서 위로 탐색
        for (int j = 0; j < 6; j++) {
            for (int i = 11; i >= 0; i--) {
                if (map[i][j] == '.') {
                	// .이 나오지 않을 때까지 반복
                	// 위로 올라가면서 뿌요가 있는지 탐색하는 거
                    int po = i;
                    while (po >= 0 && map[po][j] == '.') {
                        po--;
                    }
                    // 위로 올라가서 뿌요를 발견한 경우
                    if (po >= 0) {
                    	//맨 아래 위치에 뿌요를 넣어두고 뿌요가 있었던 곳에는 .을 채움
                        map[i][j] = map[po][j];
                        map[po][j] = '.';
                    }
                }
            }
        }
    }

 

main 코드

- while 안에서 뿌요가 터질 것이 있다면 flag true

- flag가 true이면 연쇄 +1

- 더 이상 터질 것이 없다면 flag가 false가 되고 반복 종료

private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer tokens;
	private static char map[][] = new char[12][6];
	private static int deltas[][] = {{0,-1},{1,0}, {-1,0}, {0,1}};
	private static boolean visited[][];
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		for(int i=0; i<12; i++) {
			tokens = new StringTokenizer(input.readLine());
			String row = tokens.nextToken();
			for(int j=0; j<6; j++) {
				map[i][j]=row.charAt(j);
			}
		}
        
		int count=0; //최종 횟수
        
		while(true) {
			boolean flag = false; //뿌요가 있는지 확인
			visited = new boolean[12][6];
			for(int i=0; i<12; i++){
				for(int j=0; j<6; j++) {
					//문자가 있고 방문하지 않은 점이면 bfs 호출
					if(map[i][j]!='.' && !visited[i][j]) {
						if(bfs(i,j)) { //문자가 4개이상 연결되어있다면
							flag = true;
						}
					}
					
				}
			}
			//모든 점을 돌았는데 문자가 모두 . 이거나 bfs로 4개이상 없다면
			if(!flag) break;
			
			fall();
			count++;
		}
		System.out.println(count);
	}

 

n 시간 동안 삽질하고 다시 구현하고 디버깅하고 그랬다 ㅠ_ㅠ

특히 fall 함수를 구현하는데 처음에 while을 써서 시간 초과가 났었는데 어차피 main에서 돌려주면 되니까 while을 쓰지 않아도 됐었다. 구현 많이 연습하쟈 ~