개발생각

[Baekjoon][https://www.acmicpc.net/problem/2668]

깊이 우선 탐색(DFS) 알고리즘

입력 받은 데이터가 노드로 간선을 이루고 있다고 가정 했을때,

간선의 경로가 cycle을 가진 경우 두 집합에 모두 포함된다고 볼 수 있다.

즉, 그래프에서 cycle을 가지는 경로의 정점을 찾는 문제

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

public class Main {

   static int n;
   static int[][] map;
   static boolean[] visit;
   static int cnt = 0;
   static ArrayList<Integer> result = new ArrayList<Integer>();
   
   public static void main(String[] args) {
      // TODO Auto-generated method stub
      Scanner sc = new Scanner(System.in);
      
      n = sc.nextInt();
      map = new int[n+1][n+1];
      visit = new boolean[n+1];
      
      for(int i=1;i<=n;i++) {
         int second_row = sc.nextInt();
         map[i][second_row] = 1;
      }
      
      for(int i=1;i<=n;i++) {
         for(int j=1;j<=n;j++) {
            if(map[i][j] == 1 && !visit[j]) {
               getDFS(j,i);
            }
         }
      }
      
      Collections.sort(result);
      System.out.println(cnt);
      
      for(int i = 0;i<result.size();i++)
      {
    	System.out.println(result.get(i));  
      }
   }
   
   public static void getDFS(int x, int y)
   {
      if(x==y) {
         result.add(x);
         cnt++;
      }
      
      visit[x] = true;
      
      for(int i=1;i<=n;i++) {
         if(map[x][i] == 1 && !visit[i]) {
            getDFS(i,y);
         }
         visit[i] = false;
      }
   }
}

[Baekjoon][https://www.acmicpc.net/problem/1463]

다이나믹 프로그래밍(DP) > Bottom-up 형식

풀이)

 (1) d[n] : 1 ~ N 일때 1로 만들기 위한 최소 개수를 저장.

 (2) 가장 작은 단위인 dp[1] = 0 으로 초기화 하여, dp[2] 부터 For문 처리 (Bottom-up) 형식

 (3) Math.min() 함수로 메모이제이션 해두었던 값과 현재 값의 최소값을 비교하여,

     연산을 사용하는 횟수의 최솟값을 구한다.

import java.util.Scanner;

public class baekjoon_1463 {
	static int[] dp;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		dp = new int[1000001];
		dp[1] = 0;
		
		for(int i=2;i<=n;i++) {
			dp[i] = dp[i-1] + 1;
			
			if(i%2 == 0) {
				dp[i] = Math.min(dp[i], dp[i/2]+1);
			}
			if(i%3 == 0) {
				dp[i] = Math.min(dp[i], dp[i/3]+1);
			}
		}
		
		System.out.println(dp[n]);
	}
}

[Baekjoon][https://www.acmicpc.net/problem/10026]

그래프 문제 > DFS로 풀이

풀이)

 (1) 영역을 배열값에 저장 : map[n][n] 

 (2) DFS 탐색 메소드를 두개 생성 

     - 적록색약 DFS 탐색 : GetColorWeaknessDFS()

     - 그 외 DFS 탐색 : GetDFS

     // 방문 체크 배열도 각각 선언해서 체크한다. ( visit_for_color_weakness[n][n] / visit[n][n])

 (3) current_color 변수를 선언하여 현재 좌표의 색상을 저장하였고,

     해당 값이 다음 진행 방향이랑 같은지 체크해서 DFS 탐색 트리를 적용하였다.

 (4) 적록색약의 경우 아래 코드와 같이 분기 체크하여 다음 탐색 영역이 G,R 인 경우 같은 값으로 보도록 처리.

[ Java > Code ]

import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.Scanner;

public class baekjoon_10026 {

	static int n;
	static char[][] map;
	static int[][] visit;
	static int[][] visit_for_color_weakness;
	
	static int[] xx = {-1, 0, 1, 0};
	static int[] yy = {0, 1, 0, -1};
	static char current_color;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		map = new char[n][n];
		visit_for_color_weakness = new int[n][n];
		visit = new int[n][n];
		
		int weak_color_answer = 0;
		int color_answer = 0;

		for(int i=0;i<n;i++)
		{
			String str = sc.next();
			for(int j=0;j<n;j++)
			{
				map[i][j] = str.charAt(j);
			}
		}
		
		for(int i =0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(visit[i][j] == 0)
				{
					current_color = map[i][j];
					GetDFS(i, j);
					color_answer++;
				}
				
				if(visit_for_color_weakness[i][j] == 0)
				{
					current_color = map[i][j];
					GetColorWeaknessDFS(i, j);
					weak_color_answer++;
				}
			}
		}
		
		System.out.print(color_answer + " " + weak_color_answer);
	}

	// 적록색약 적용 DFS 탐색 (Red == Green)
	public static void GetColorWeaknessDFS(int x, int y)
	{
		visit_for_color_weakness[x][y] = 1;
		
		for(int i=0;i<4;i++)
		{
			int mx = x + xx[i];
			int my = y + yy[i];
			
			if(current_color == 'G' || current_color == 'R')
			{
				if(mx >= 0 && mx < n && my >= 0 && my < n && visit_for_color_weakness[mx][my] == 0 && (map[mx][my] == 'G' || map[mx][my] == 'R'))
				{
					GetColorWeaknessDFS(mx, my);
				}
			}
			else
			{
				if(mx >= 0 && mx < n && my >= 0 && my < n && visit_for_color_weakness[mx][my] == 0 && map[mx][my] == 'B')
				{
					GetColorWeaknessDFS(mx, my);
				}
			}			
		}
	}
	
	// 적록색약 아닌 경우 DFS 탐색
	public static void GetDFS(int x, int y)
	{
		visit[x][y] = 1;
		
		for(int i=0;i<4;i++)
		{
			int mx = x + xx[i];
			int my = y + yy[i];
			
			if(mx >= 0 && mx < n && my >= 0 && my < n && visit[mx][my] == 0 && map[mx][my] == current_color)
			{
				GetDFS(mx, my);
			}
		}
	}
}

[Baekjoon][https://www.acmicpc.net/problem/2667]

기본적인 DFS 그래프 문제

풀이)

  (1) 입력한 영역을 배열로 저장: map[n]

  (2) getDFS 메소드로 DFS 탐색 처리

       - visit[n][n] : 1인 구간은 탐색 완료 / 0 은 이동 가능

  (3) ←,↑,→,↓ 방향 순으로 체크하며 getDFS 내 재귀함수로 탐색 시, 연결되어 있는 단지로 파악하여

      연결 값 증가되도록 처리 (connected++)

  (4) main 메소드 내 > 호출하는 getDFS는 연결이 아닌 단지를 처음 발견 (map[n][n] == 1 && visit[n][n] == 0)

      이므로 connected 값 초기 화 및 총 단지 값(complex_cnt)을 +1 처리한다.

이번 알고리즘을 풀면서 다시 체크해야할 부분은 단지 정보를 입력하는 부분으로

map[n] : 1차 배열에 String ar = sc.nextLine() 으로 입력 받은 후, 

이를 toCharArray(); 메소드를 이용하여 배열로 처리되도록 처리하였다.

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class baekjoon_2667 {

	static int n;
	static int[][] map;
	static int[][] visit;
	static int complex_cnt = 0;
	static int connected = 0;
	static ArrayList<Integer> connected_complex; 
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		map = new int[n][n];
		visit = new int[n][n];
		connected_complex = new ArrayList<Integer>();
		
		sc.nextLine();
		
		for(int i =0;i<n;i++) {
			String ar = sc.nextLine();
			char[] visit = ar.toCharArray();
			
			for(int j=0;j<n;j++) {
				map[i][j] = (int)visit[j] - '0';
			}
		}
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[i][j] == 1 && visit[i][j] != 1) {
					getDFS(i, j);
					
					complex_cnt++;
					connected_complex.add(connected);
					connected = 0;
				}
			}
		}
		
		System.out.println(complex_cnt);
		Collections.sort(connected_complex);
		for(int i=0;i<connected_complex.size();i++) {
			System.out.println(connected_complex.get(i));
		}
	}
	
	public static void getDFS(int x, int y)
	{
		visit[x][y] = 1;
		connected++;
		
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0, -1};
		
		for(int i=0;i<4;i++)
		{
			int mx = x + xx[i];
			int my = y + yy[i];
			
			if(mx >= 0 && mx < n && my >= 0 && my < n && map[mx][my] == 1 && visit[mx][my] != 1) {
				getDFS(mx, my);
			}
		}
	}
}

[Baekjoon][https://www.acmicpc.net/problem/2583]

기본적인 그래프 문제

풀이)

  (1) 이미지와 같이 노출을 하기 위해 m을 y축 n을 x 축으로 받아서 처리 : 배열 map[n][m]로 선언

  (2) 칠해진 직사각형 내 좌표의 값은 DFS 처리 시 해당 영역을 접근하지 않게끔 값 : '1'로 선언

  (3) 2번 내용 처리 시 아래 이미지와 같이 체크된 직사각형 영역은 1 그렇지 않은 부분은 0 으로 처리된다.

   (4) DFS를 이용하여 이미 방문한 좌표와 (배열 visited[n][m] = 1) 과 좌표의 값이 1인 (map[n][m] = 1)

       부분을 제외하여 하나씩 값을 체크

map[n][m] : 배열로 직사각형 좌표 저장 // 1 : 빗줄 그어진 영역, 0 : 그 외

visited[n][m] : 이미 방문한 지역 저장 // 1 : 방문, 0 : 미방문

DFS 그래프로 <왼쪽, 위, 아래, 오른쪽 > 방향 이동

// int mx = x+xx[i]; int my = y+yy[i];

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

public class Main {

   static int n;
   static int m;
   static int k;
   static int[][] map;
   static int[][] visited;
   static int space;
   static int space_cnt;
   
   public static void main(String[] args) {
      // TODO Auto-generated method stub
      Scanner sc = new Scanner(System.in);
      
      m = sc.nextInt(); // y축
      n = sc.nextInt(); // x축
      k = sc.nextInt(); // 개수
      map = new int[n][m];
      visited = new int[n][m];
      
      for(int i=0; i<k; i++) {
         int start_y = sc.nextInt();
         int start_x = sc.nextInt();
         int end_y = sc.nextInt();
         int end_x = sc.nextInt();
         
         SetVisited(start_y, start_x, end_y, end_x);
      }
      
      ArrayList<Integer> ar_space_cnt = new ArrayList<Integer>();
      
      for(int i=0;i<m;i++) {
         for(int j=0;j<n;j++) {
            if(map[j][i] == 0 && visited[j][i] == 0) {
               space++;
               GetDfs(j, i);
               ar_space_cnt.add(space_cnt);
               space_cnt = 0;
            }
         }
      }
      
      Collections.sort(ar_space_cnt);
      
      System.out.println(space);
      if(ar_space_cnt.size() == 0 ) System.out.println("0");
      for(int i=0;i<ar_space_cnt.size();i++) {
         System.out.print(ar_space_cnt.get(i) + " ");
      }
   }
   
   // map[][] 색칠된 영역 1로 설정
   public static void SetVisited(int start_y, int start_x, int end_y, int end_x) {
      for(int i=start_y;i<end_y;i++) {
         for(int j=start_x;j<end_x;j++) {
        	 map[i][j] = 1;
         }
      }
   }
   
   // DFS 로직 처리
   public static void GetDfs(int x, int y) {
      visited[x][y] = 1;
      space_cnt++;

      int[] xx = {-1, 0, 1, 0};
      int[] yy = {0, 1, 0, -1};
      
      for(int i=0; i<4; i++) {
         int mx = x+xx[i];
         int my = y+yy[i];
         
         if(mx >=0 && mx < n && my >= 0 && my < m && map[mx][my] == 0 && visited[mx][my] == 0) {
        	 GetDfs(mx, my);
         }
      }
   }
}