개발 다이어리

코드

import java.util.ArrayList;
import java.util.Collections;

/**
 * 벽돌은 가장 넓은 것이 아래에 위치
 * 그리고 가장 무거운 것일 수록 아래 위치
 */
public class 가장높은탑쌓기{

	static class Brick implements Comparable<Brick>{
		public final int width, heigth, weight;
		public Brick(int width, int heigth, int weight) {
			this.width = width;
			this.heigth = heigth;
			this.weight = weight;
		}
		public int compareTo(Brick o){
			return o.width-this.width;
		}
	}
	
	static int[] dy;
	static ArrayList<ArrayList<Brick>> list;
	
	public static void main(String[] args){
		int[][] input = 
			{
					{25, 3, 4 }
					,{4 ,4 ,6  }
					,{9 ,2 ,3  }
					,{16, 2, 5 }
					,{1 ,5 ,2  }
			};
		int n=input.length;
		
		ArrayList<Brick> arr=new ArrayList<>();
		
		dy=new int[n];
		for(int i=0; i<n; i++){
			int a= input[i][0] ;
			int b= input[i][1] ;
			int c= input[i][2] ;
			arr.add(new Brick(a, b, c));
		}
		System.out.print(solution(arr));
	}
	
	static int solution(ArrayList<Brick> arr){
		//너비 순으로 내림차순
		Collections.sort(arr);
		dy[0]=arr.get(0).heigth;
		int answer= dy[0];
		
		//높이 비교 1부터
		for(int i=1; i<arr.size(); i++){
			//높이 tmp
			int max_h=0;
			//이전 벽돌 비교
			for(int j=i-1; j>=0; j--){
				//무게는 j가 커야한다. 그리고 그 중에 제일 높은 값을 구한다.
				if(arr.get(j).weight > arr.get(i).weight && dy[j]>max_h){
					max_h=dy[j];
				}
			}
			//제일 높은 값을 구했으니, 그 값에 나의 높이를 더 한다.
			dy[i]=max_h+arr.get(i).heigth;
			//지금까지 높이 중 가장 큰 높이를 구한다.
			answer=Math.max(answer, dy[i]);
		}
		return answer;
	}
}

결과

10

이전 최대부분증가수열과 거의 같다. 

일부 특수화가 됐을 뿐이다.

코드

import java.util.Arrays;

public class 최대부분증가수열연습 {
	static int dy[];
	
 	public static void main(String[] args) {
 		//수열
		int[] arr = {5, 3, 7, 8, 6, 2, 9, 4};
		System.out.println(solution(arr));
	}
	static int solution(int[] arr) {
		int answer = 0;
		dy = new int[arr.length];
		dy[0] = 1;
		//수열 순회
		for(int i=1;i<arr.length;i++) {
			//수열 수 저장
			int max = 0;
			//현재 수열 이전 값 중 작은 값있는지 탐색
			for(int j=i;j>=0;j--) {
				//현재 수열보다 작은 값 있으면, 거기에 저장된 수열 횟수 저장
				if(arr[i]>arr[j]) {
					max = Math.max(max, dy[j]);
				}
			}
			//구해진 수열 수에 +1
			dy[i] = max+1;
			//최종적으로 가장 횟수 많은 부분 수열을 구함
			answer = Math.max(answer, dy[i]);
		}
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(dy));
		return answer;
	}
}

결과

[5, 3, 7, 8, 6, 2, 9, 4]
[1, 1, 2, 3, 2, 1, 4, 2]
4

9가 있는 위치를 기준으로 설명

이 기준으로 탐색을 시작

그 값에 +1을 한 것

왜 3을 찾아서 +1을 했는가?

8을 기준으로 하면 최대 부분 증가 수열은 3이다.

5-7-8 or -3-7-8  3개

9 값이전에서 가장 큰 최대 부분 증가 수열 수는 3이다.

그 값에 +1을 한 것

바텀업 방식으로 값을 구한 것이다.

문제의 본질을 유지한 상태로 작은 케이스부터 큰 케이스를 탐색하는 방식

코드

public class 돌다리건너기 {
	static int[] dy;
	static int[] memo;
	
	static int cnt = 0;
	
	public static void main(String[] args) {
		int goal = 10; // 돌다리 개수
		goal +=1; //1개를 더한다
		
		dy = new int[goal+1];
		memo = new int[goal+1];
		
		long start = System.nanoTime();
		System.out.println("answer = " +dy(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
		start = System.nanoTime();
		cnt=0;
		System.out.println("answer = "+noDy(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
		start = System.nanoTime();
		cnt=0;
		System.out.println("answer = "+noDyMemo(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
	}

	private static int dy(int goal) {
		dy[1] = 1;
		dy[2] = 2;
		for(int i=3;i<=goal;i++,cnt++) {
			dy[i] = dy[i-1]+dy[i-2];
		}
		return dy[goal];
	}
	
	static int noDy(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else return noDy(goal-1)+noDy(goal-2);
	}
	
	static int noDyMemo(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else if(memo[goal]>0) return memo[goal];
		else return memo[goal]=noDyMemo(goal-1)+noDyMemo(goal-2);
	}
}

결과

answer = 144
9
765600
answer = 144
177
47600
answer = 144
19
21900

계단 같은 경우는 계단에 도착한게 도착지지만, 

돌다리의 경우 건너편을 건너기 위한 돌다리 개수를 받았기 때문에 최종 돌다리가 목적지가 아니라 +1 한 건너편이 목적지다

코드

//계단을 오를 땐 한 번에 1개, 2개씩 오를 수 있다.

public class 계단오르기 {
	static int[] dy;
	static int[] memo;
	
	static int cnt = 0;
	
	public static void main(String[] args) {
		int goal = 10; //10계단까지 가는 방법
		dy = new int[goal+1];
		memo = new int[goal+1];
		
		System.out.println("answer = " +dy(goal));
		System.out.println(cnt);
		cnt=0;
		System.out.println("answer = "+noDy(goal));
		System.out.println(cnt);
		cnt=0;
		System.out.println("answer = "+noDyMemo(goal));
		System.out.println(cnt);
		
	}

	private static int dy(int goal) {
		dy[1] = 1;
		dy[2] = 2;
		for(int i=3;i<=goal;i++,cnt++) {
			dy[i] = dy[i-1]+dy[i-2];
		}
		return dy[goal];
	}
	
	static int noDy(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else return noDy(goal-1)+noDy(goal-2);
	}
	
	static int noDyMemo(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else if(memo[goal]>0) return memo[goal];
		else return memo[goal]=noDyMemo(goal-1)+noDyMemo(goal-2);
	}
}

결과

answer = 89
8
answer = 89
109
answer = 89
17

큰 문제의 본질을 그대로 유지한 상태로 작게 축소하여 계산해 이를 이용해 큰 문제를 해결하는 방법

동적 계획법으로 풀었을 때는 8번 반복(1,2는 수동으로 입력했음) 

그냥 큰 문제로 바로 풀었을 경우 109번의 반복(재귀)

큰 문제를 메모이제이션으로 풀었을 경우 17번의 반복(재귀)

public class 계단오르기 {
	static int[] dy;
	static int[] memo;
	
	static int cnt = 0;
	
	public static void main(String[] args) {
		int goal = 50;
		dy = new int[goal+1];
		memo = new int[goal+1];
		
		long start = System.nanoTime();
		System.out.println("answer = " +dy(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
		start = System.nanoTime();
		cnt=0;
		System.out.println("answer = "+noDy(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
		start = System.nanoTime();
		cnt=0;
		System.out.println("answer = "+noDyMemo(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
	}

	private static int dy(int goal) {
		dy[1] = 1;
		dy[2] = 2;
		for(int i=3;i<=goal;i++,cnt++) {
			dy[i] = dy[i-1]+dy[i-2];
		}
		return dy[goal];
	}
	
	static int noDy(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else return noDy(goal-1)+noDy(goal-2);
	}
	
	static int noDyMemo(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else if(memo[goal]>0) return memo[goal];
		else return memo[goal]=noDyMemo(goal-1)+noDyMemo(goal-2);
	}
}

answer = -1109825406
48
648700
answer = -1109825406
-597265727
40278105300
answer = -1109825406
103
37300

50을 줬을때 반복횟수와 소요시간

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.stream.Stream;

public class 다익스트라연습 {
	private static class Edge implements Comparable<Edge>{
	    private final int vex;
	    private final int cost;
		
		private Edge(int vex, int cost) {
	        this.vex = vex;
	        this.cost = cost;
	    }
	    public int compareTo(Edge ob){
	        return Integer.compare(this.cost,ob.cost);
	    }
	    public String toString() {
	    	return "["+vex+", "+cost+"]";
	    }
	}
	static ArrayList<ArrayList<Edge>> graph;
	static int[] dis;
	
	static void sol(int v) {
		//내부적으로 이분검색을 사용해 시간 복잡도가 log n
		PriorityQueue<Edge> q = new PriorityQueue<>();
		//시작 정점은 거리 0
		dis[v] = 0;
		//시작 정점은 비용 0
		q.offer(new Edge(v, 0));
		while(!q.isEmpty()) {
			//자료구조 상 가장 비용이 작은 정점이 나온다.
			Edge cur = q.poll();
			//현재 가장 작은 비용이 이미 저장된 비용보다 크면 확인할 필요가 없다.
			if(cur.cost>dis[cur.vex]) continue;
			//graph.get(cur.vex)은 n번 수행된다.
			//graph.get(cur.vex) 결과로 나온 Edge는 최소 n번 이상 수행된다.
			for(Edge next : graph.get(cur.vex)) {
				//다음 경로 비용 계산 시작
				//다음 경로에 이미 저장된 비용 > 현재까지 누산된 비용 + 다음 경로까지 비용
				if(dis[next.vex] > cur.cost + next.cost ) {
					dis[next.vex] = cur.cost + next.cost;
					//중요_ 현재까지 누산된 비용을 다음 경로까지 물고간다.
					q.offer(new Edge(next.vex, cur.cost + next.cost));
				}
			}
		}
	}
	
	public static void main(String[] args){
		//{간선시작, 간선끝, 가중치}
		int[][] arr = 
			{{1, 2, 12}
			,{1, 3, 4 }
			,{2, 1, 2 }
			,{2, 3, 5 }
			,{2, 5, 5 }
			,{3, 4, 5 }
			,{4, 2, 2 }
			,{4, 5, 5 }
			,{6, 4, 5 }	};
		
		graph = new ArrayList<ArrayList<Edge>>();
		graph.add(new ArrayList<>()); // 0 번 미사용
		System.out.println("==정점 만큼 골라내기==");
		Arrays.stream(arr)
			.flatMap(data -> Stream.of(data[0],data[1]))
			.distinct()
			.peek(data -> System.out.print(data+", "))
			.forEach( data -> graph.add(new ArrayList<>()));
		//거리비용 저장 배열
		dis = new int[graph.size()];
		Arrays.fill(dis, Integer.MAX_VALUE);
		
		System.out.println("\n==간선 정보==");
		Arrays.stream(arr)
			.peek(data->System.out.println(data[0]+"->" +data[1]+" 가중치:"+data[2]))
			.forEach(data ->graph.get(data[0]).add(new Edge(data[1], data[2])));
		
		sol(1);
		System.out.println("== 정점 별 최소 비용 ==");
		for(int i=2; i<graph.size(); i++){
			if(dis[i]!=Integer.MAX_VALUE) System.out.println(i+" : "+dis[i]);
			else System.out.println(i+" : impossible");
		}
	}
}

결과

==정점 만큼 골라내기==
1, 2, 3, 5, 4, 6, 
==간선 정보==
1->2 가중치:12
1->3 가중치:4
2->1 가중치:2
2->3 가중치:5
2->5 가중치:5
3->4 가중치:5
4->2 가중치:2
4->5 가중치:5
6->4 가중치:5
== 정점 별 최소 비용 ==
2 : 11
3 : 4
4 : 9
5 : 14
6 : impossible

우선순위 큐를 사용해 시간 복잡도를 줄인 것이 핵심

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		ArrayList<Person> list = new ArrayList<Main.Person>();
		int size = sc.nextInt();
		for (int i = 0; i < size; i++) {
			list.add( T.new Person( sc.nextInt(), sc.nextInt() ) );
		}
		Collections.sort(list,Comparator.reverseOrder());
		
		System.out.println(T.solution(list));
		
		sc.close();
	}
	
	private int solution(ArrayList<Person> list) {
		int max = Integer.MIN_VALUE;
		int cnt = 0;
		
		for (Person person : list) {
			if(max<person.weight) {
				cnt++;
				max = person.weight;
			}
		}
		return cnt;
	}

	class Person implements Comparable<Person>{
		int height;
		int weight;
		public Person(int height, int weight) {
			super();
			this.height = height;
			this.weight = weight;
		}
		@Override
		public int compareTo(Person o) {
			return Integer.compare(this.height, o.height);
		}
		@Override
		public String toString() {
			return height+" "+weight;
		}
	}
	
}

입력

5
172 67
183 65
180 70
170 72
181 60

결과

3

넓은 의미의 그리디 알고리즘, 당장 최선의 선택을 함

키로 정렬해두면, 몸무게만 고려하면 됨

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 피자배달거리DFS {
	
	static int[] combi; //경우의 수를 채울 배열
	
	static List<Point> hs = new ArrayList<피자배달거리DFS.Point>();
	static List<Point> pz = new ArrayList<피자배달거리DFS.Point>();
	
	static int answer = Integer.MAX_VALUE;
	static int len,n,m;
	
	public static void main(String[] args) {
		피자배달거리DFS T = new 피자배달거리DFS();
		n = 4; //2차원 배열 크기
		m = 4; // 피자 집 선택 수
		int[][] board =  
			{{0, 1, 2, 0}
			,{1, 0, 2, 1}
			,{0, 2, 1, 2}
			,{2, 0, 1, 2}};
		
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==2) { // 피자집은 2
					pz.add(new Point(i, j));
				}else if(board[i][j]==1) {// 가정집 1
					hs.add(new Point(i, j));
				}//이외는 빈 곳
			}
		}
		len = pz.size();
		combi = new int[m];//경우의 수 배열 
		
		T.DFS(0,0);
		System.out.println(answer);
		
	}
	
	//재귀는 피자집 기준으로 쌓고 있다.
	void DFS(int L, int s) {
		if(L==m) { // 경우의 수 다 채움
			System.out.println(Arrays.toString(combi));
			int sum = 0;
			for(Point h : hs) {
				int dis = Integer.MAX_VALUE;
				//다 찬 경우의 수 배열에는 피자집 위치 정보가 있다.
				for(int i : combi) {
					dis = Math.min(dis, Math.abs(h.x-pz.get(i).x)+Math.abs(h.y-pz.get(i).y)) ;
				}
				sum += dis;
			}
			answer = Math.min(answer, sum);
		} else {
			for (int i = s; i < len; i++) {
				combi[L] = i;
				DFS(L+1, i+1);
			}
		}
	}
	
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

결과

[0, 1, 2, 3]
[0, 1, 2, 4]
[0, 1, 2, 5]
[0, 1, 3, 4]
[0, 1, 3, 5]
[0, 1, 4, 5]
[0, 2, 3, 4]
[0, 2, 3, 5]
[0, 2, 4, 5]
[0, 3, 4, 5]
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 4, 5]
[1, 3, 4, 5]
[2, 3, 4, 5]
6

핵심은 사전처리로 피자 가게와 가정집 위치를 수집해 두 개 집단으로 묶는다.

이후 두 집단간에 DFS로 경우의 수를 구한다.

나머지는 부차적인 코드로 문제로 공식을 알려준다.

코드

import java.util.LinkedList;
import java.util.Queue;

class 섬나라아일랜드BFS {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	static Queue<Point> q = new LinkedList<섬나라아일랜드BFS.Point>();
	
	
	static void BFS(int[][] board,int x, int y) {
		
		q.offer(new Point(x, y));
		while(!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Point p = q.poll();
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j];
					int ny = p.y+dy[j];
					if(nx>=0&&nx<n && ny>=0&&ny<n && board[nx][ny]==1) {
						board[nx][ny] = 99;
						q.offer(new Point(nx, ny));
					}
				}
			}
		}
		
		
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1 ) {
				board[nx][ny] = 99;
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 99;
					BFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	static  class Point{
		int x,y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args){
		섬나라아일랜드BFS T = new 섬나라아일랜드BFS();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
99 99  0  0  0  1  0 
 0 99 99  0  1  1  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
 1  1  0 99 99  0  0 
 1  0  0  0 99  0  0 
 1  0  1  0 99  0  0 

===4번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0  1  0 99  0  0 

===5번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0 99  0 99  0  0 

5

단순히 DFS=>BFS로 해결한 코드

코드

class 섬나라아일랜드 {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	
	static void DFS(int[][] board,int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1) {
				board[nx][ny] = 0;
				DFS(board,nx,ny);
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 0;
					DFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	

	public static void main(String[] args){
		섬나라아일랜드 T = new 섬나라아일랜드();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
 0  0  0  0  0  1  0 
 0  0  0  0  1  1  0 
 0  0  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 1  1  0  0  0  0  0 
 1  0  0  0  0  0  0 
 1  0  1  0  0  0  0 

===4번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  1  0  0  0  0 

===5번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 

5

주어진 2차원 배열(지도)에 1 표기가 섬이다. 섬은 상하좌우 좌상우상좌하우하 이렇게 8방향으로 연결되어 있다.

solution은 지도를 순회하여 섬을 탐색한다.

DFS는 섬을 지도에서 소거한다. 이렇게 되면 자연스럽게 solution이 다시 순회를 시작해도 같은 섬 중복이 날수가 없다.

여기서는 1이면 섬으로 판단한다. 그래서 가시성을 위해 지워진 섬을 99로 변경해 어떻게 동작하는지 좀 더 명확하게 볼 수 있다.

코드

class 섬나라아일랜드 {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	
	static void DFS(int[][] board,int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1 ) {
				board[nx][ny] = 99;
				DFS(board,nx,ny);
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 99;
					DFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	

	public static void main(String[] args){
		섬나라아일랜드 T = new 섬나라아일랜드();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
99 99  0  0  0  1  0 
 0 99 99  0  1  1  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
 1  1  0 99 99  0  0 
 1  0  0  0 99  0  0 
 1  0  1  0 99  0  0 

===4번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0  1  0 99  0  0 

===5번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0 99  0 99  0  0 

5

코드

import java.util.*;

class Main {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board, dis;
	static int n, m;
	static Queue<Point> Q=new LinkedList<>();
	
	static void BFS2(){
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				Point p = Q.poll();
				
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j];
					int ny = p.y+dy[j];
					
					if(nx>=0&&nx<n  && ny>=0&&ny<m && board[nx][ny]==0) {
						board[nx][ny]= 1;
						Q.offer(new Point(nx, ny));
						dis[nx][ny] =dis[p.x][p.y]+1;
					}
				}
			}
		}
	}
	
	public static void main(String[] args){
		m=6; //가로 크기
		n=4; //세로 크기
		board=new int[n][m];
		dis=new int[n][m];
		
		int[][] tmp = 
			{{0, 0, -1, 0, 0, 0}
			,{0, 0, 1, 0, -1, 0}
			,{0, 0, -1, 0, 0, 0}
			,{0, 0, 0, 0, -1, 1}};
		
		board = tmp.clone();
		
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(board[i][j]==1) Q.offer(new Point(i, j));
				//출발점이 여러개라 미리 넣어둠
			}
		}
		
		BFS2();
		
		//0이 하나라도 존재하면 토마토가 모두 익지 못하는 상황
		long count = Arrays.stream(board)
		      .flatMapToInt(Arrays::stream)
		      .filter(value->value==0)
		      .count();
		if(count>0) System.out.println(-1);
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==0) {
					System.out.println(-1);
					return;
				}
			}
		}
		
		// 만약 처음부터 모두 익어있다면 자연스럽게 0 출력될 것
		int value = Integer.MIN_VALUE;
		for (int i = 0; i < dis.length; i++) {
			for (int j = 0; j < dis[i].length; j++) {
				value = Math.max(value, dis[i][j]);
			}
		}
		System.out.println(value);
		for (int[] arr : dis) {
			for (int val : arr) {
				System.out.printf("%2s ",val);
			}
			System.out.println();
		}
		
	}
	static class Point{
		public int x, y;
		Point(int x, int y){
			this.x=x;
			this.y=y;
		}
	}
}

결과

4
 3  2  0  2  3  3 
 2  1  0  1  0  2 
 3  2  0  2  2  1 
 4  3  4  3  0  0

전부 똑같다. 다른 점은 시작점이 여러 개라면 미리 큐에 넣어둔다. 그 차이가 전부다.

문제에서 시작점인 것에 위치값을 준게 아니라 미리 board[x][y] = 1 같이 넣어뒀기에 시작 시 출발 값에 1을 체크할 필요 없다.