Yong's Tech Story

https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제 풀이 (JAVA)

import java.util.*;

class Solution {
    static List<ArrayList<Integer>> graph = new ArrayList<>(); // 인접리스트(그래프)
    static boolean [] visited; // 방문여부
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        visited = new boolean[n];
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<Integer>()); // 인접리스트 생성
        }
        for(int i=0; i<computers.length; i++){
            for(int j=0; j<computers[i].length; j++){
                if(i != j && computers[i][j]==1){
                    graph.get(i).add(j); //인접리스트(그래프 변수 삽입)
                }
            }
        }
        
        // DFS 반복
        for(int i=0; i<n; i++){
            if(visited[i] == false){
                dfs(i);
                answer++; // 네트워크 개수 카운트 증가
            }
        }
        
        
        return answer;
    }
    // DFS 함수
    public static void dfs(int N){
        visited[N] = true;
        for(Integer next : graph.get(N)){
            if(visited[next] == false){
                visited[next] = true;
                dfs(next);
            }
        }
    }
}

결론

: 해당 문제는 인접리스트(그래프)와 DFS를 사용하여 네트워크에 연결된 개수를 구하는 문제이다. 인접리스트 공식과 문제의 접근을 DFS 문제로 접근 할 수 있다면 어렵지 않은 문제이다.

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

문제 풀이 (JAVA) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr; // 이차원 배열
	static int totalCnt; // 영역의 총 개수
	static boolean[][] visited; // 방문 여부 배열
	static int size = 0; // 영역의 넓이
	static int[] dx = { 1, 0, -1, 0 }; // 4방향 
	static int[] dy = { 0, 1, 0, -1 }; 
	static int M; // 행 개수
	static int N; // 열 개수

	public static void main(String[] args) throws IOException {
		// 영역 구하기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());// 행 개수
		N = Integer.parseInt(st.nextToken());// 열 개수
		int K = Integer.parseInt(st.nextToken());// 입력 줄

		arr = new int[M][N];
		visited = new boolean[M][N];

		List<Integer> list = new ArrayList<>(); // 영역 넓이 저장 리스트

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());

			int lx = Integer.parseInt(st.nextToken()); // 왼쪽 꼭짓점 X
			int ly = Integer.parseInt(st.nextToken()); // 왼쪽 꼭짓점 Y
			int rx = Integer.parseInt(st.nextToken()); // 오른쪽 꼭짓점 X
			int ry = Integer.parseInt(st.nextToken()); // 오른쪽 꼭짓점 Y
			
            for (int x = ly; x < ry; x++) { // 배열의 x는 꼭짓점 Y
				for (int y = lx; y < rx; y++) { // 배열의 y는 꼭짓점 X
					arr[x][y] = 1; // 색칠 된 도형의 경우 1로 선언
				}
			}
		}

		for (int x = 0; x < M; x++) {
			for (int y = 0; y < N; y++) {
  				// dfs에서 연결 되지 않은 0으로 x,y를 탐색한다.
				if (visited[x][y] == false && arr[x][y] == 0) {
					size = 1; // 현재 위치 사이즈 ==1 로 초기화
					visited[x][y] = true;
					totalCnt++; // if조건에 걸렸을때 하나의 영역의 시작이다.
					dfs(x, y);

					list.add(size); // dfs 종료 시 계산된 사이즈 추가
				}
			}
		}

		Collections.sort(list); // 오름차순 정렬

		System.out.println(totalCnt);
		for (Integer n : list) {
			System.out.print(n + " ");
		}
	}

	private static void dfs(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i]; // 다음 탐색할 X
			int ny = y + dy[i]; // 다음 탐색할 Y
			if (nx >= 0 && nx < M && ny >= 0 && ny < N && visited[nx][ny] == false && arr[nx][ny] == 0) {
				visited[nx][ny] = true;
				size++;
				dfs(nx, ny);
			}
		}
	}

}

문제 풀이

1. 해당 문제는 영역을 구하는 문제로 색칠된 도형의 넓이가 아닌 색칠하지 않은 도형의 넓이를 구하는 문제이다.

2. 문제에서 제시 되는 꼭짓점의 도형맵을 아래로 뒤집게 되면, 입력받은 꼭짓점과 이차원 배열의 (x,y)가 일치하게 된다.

3. 단, 오른쪽 꼭짓점의 경우, 입력 꼭짓점 rx-1, ry-1까지 반복문을 계산하여 도형의 넓이를 구해야 일치한다.

4. 나머지는 기존의 dfs 공식을 사용한다.(경계값 체크 필수)

결론

: 해당 문제는 dfs를 변형한 문제로, 꼭짓점의 위치를 이차원 배열의 위치와 매핑시켜 색칠 된 도형의 넓이를 구하는 것이 핵심이다. 입력 변수를 받아 arr를 잘 입력하였다면, 기존의 dfs 공식을 써서 풀 수 있다.

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

문제 풀이 (JAVA) 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static List<ArrayList<Integer>> graph = new ArrayList<>(); // 인접 그래프 리스트
	static int[][] arr; // 이차열 배열 변수
	static boolean[] visited; // 방문 여부 배열 변수
	static int N;

	public static void main(String[] args) throws IOException {
		// 경로 찾기(그래프 탐색)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		arr = new int[N + 1][N + 1];

		for (int i = 0; i <= N; i++) {
        	// 인접 그래프 리스트 생성자 추가
			graph.add(new ArrayList<>());
		}

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				int num = Integer.parseInt(st.nextToken());
				if (num == 1) {
					graph.get(i).add(j); // 인접 그래프 리스트 요소 추가(a->b 간선)
				}
			}
		}
		
        // 1부터 N까지 경로 dfs 반복하여 탐색
		for (int i = 1; i <= N; i++) {
			visited = new boolean[N + 1];
			dfs(i, i);
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(arr[i][j] + " ");

			}
			System.out.println();
		}
	}

	private static void dfs(int n, int start) {
		for (Integer next : graph.get(n)) {
			if (visited[next] == false) {
				visited[next] = true;
				arr[start][next] = 1; // 1부터 ~ N까지 start를 저장하여 dfs 배열에 저장
				dfs(next, start);
			}
		}
	}

}

문제 풀이

1. 경로를 탐색하는 문제로 다양한 방법이 있지만 DFS를 사용

2. 처음에는 dfs함수의 visited=true -> dfs -> visited=false로 하였지만, 시간 초과 발생

3. visited를 false로 할 필요가 없는 이유는 start 노드에서 N까지 갈 수 있는지만 보면 되기 때문에 모든 경우의 N을 구할 필요가 없기 때문이다.

4. 따라서 1~N까지 start 노드를 넘겨 dfs가 돌면서 방문하였을때, 연결이 된 노드로 dfs가 끝나면 간선간의 연결 여부를 알 수 있다.

결론

: 문제의 접근을 모든 경우의 수 가 아닌 1~N까지의 숫자가 다른 숫자 노드와 연결 되는지 여부를 생각하여 접근한다면 쉬웠을 것이다. 다양한 경우의 경로 탐색 문제를 많이 풀어봐야겠다는 생각을 하였다.

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

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon1260 {
	static List<ArrayList<Integer>> graph = new ArrayList<>(); // 인접리스트 그래프
	static boolean[] visited; // 방문 여부 배열
	static List<Integer> bfslist = new ArrayList<>(); // bfs 노드를 저장할 리스트
	static List<Integer> dfslist = new ArrayList<>(); // dfs 노드를 저장할 리스트

	public static void main(String[] args) throws IOException {
		// DFS와 BFS
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 정점의 개수
		int M = Integer.parseInt(st.nextToken()); // 간선의 개수
		int V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점의 번호

		visited = new boolean[N + 1];

		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			// 양방향 그래프 세팅
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		// 그래프 오름차순 정렬
		for (int i = 1; i <= N; i++) {
			Collections.sort(graph.get(i));
		}

		bfs(V);

		visited = new boolean[N + 1];

		dfs(V);

		for (int i = 0; i < bfslist.size(); i++) {
			System.out.print(dfslist.get(i) + " ");
		}
		System.out.println();

		for (int i = 0; i < bfslist.size(); i++) {
			System.out.print(bfslist.get(i) + " ");
		}
	}

	private static void bfs(int num) {
		Queue<Integer> queue = new LinkedList<>();

		queue.offer(num);
		visited[num] = true;

		while (!queue.isEmpty()) {
			int cur = queue.poll();

			bfslist.add(cur);

			for (Integer next : graph.get(cur)) {
				if (visited[next] == false) {
					visited[next] = true;
					queue.offer(next);
				}
			}
		}
	}

	private static void dfs(int num) {
		visited[num] = true;
		dfslist.add(num);
		for (Integer next : graph.get(num)) {
			if (visited[next] == false) {
				dfs(next);
			}
		}
	}

}

주요 핵심 포인트

1. 위 문제는 BFS와 DFS의 기본을 알고 있는지를 묻는 문제로 개념적인 공부가 필요하다.

2. 출력값은 오름 차순을 기준으로 뽑아야 하기 때문에 그래프의 리스트를 오름차순으로 정렬하였다.

3. bfs 함수의 경우 큐를 사용하여 기본적인 bfs 함수를 갖추었고, 출력하고자 하는 값을 bfslist에 순서대로 저장하였다.

4. dfs 함수의 경우도 dfs의 기본 원리에 맞춰서 깊이 탐색을 진행하였다.

개선해야할 사항

: bfs와 dfs의 값을 출력하기 위하여 리스트를 선언하였으나, 리스트가 아니라 출력을 사용하여 푸는 방법도 있을 듯하다. 필자는 main에서 값을 출력하는 것을 선호하여 리스트로 만들었지만, 함수에서 print() 처리를 하는 방법도 생각해보아야 겠다.