[BAEKJOON] 유형별 문제풀이(1) | 그래프 DFS & BFS | JAVA

문제 유형을 파악하는 감이나 유형별 문제풀이 요령이 부족한듯하여 지난주부터 백준 문제풀이를 시작했다. 원래 계획은 주마다 한 유형씩 뽀개기였으나.. 지난주처럼 연휴가 많지 않고서야 시간내기가 어렵다. 그래도 이렇게 한 알고리즘에 대해 기초 문제부터 응용 문제까지 한번 훑고나니 도움이 된다. 백준에 다양한 문제집들이 있지만 뭐가 좋은지도 모르겠고, 문제가 워낙 많아서 그냥 일단 단계별 풀이의 알고리즘을 선택해 시작했다. 여러 문제가 있고, 내 문제집을 만들어 추가중이긴 하나 그 중에서도 다시 봐야할 문제들만 포스팅할 예정 ✍🏻

문제 > 단계별로 풀어보기 https://www.acmicpc.net/step

 

---

 

24479, 24480. 알고리즘 수업 - 깊이 우선 탐색 1, 2

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

정점들의 방문 순서를 출력하는 문제로, 24479와 24480 문제의 차이점은 인접 정점의 방문 순서가 오름차순인지 내림차순인지 그 차이뿐이다.

static int n, m, r;
static int cnt = 1;
static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
static boolean[] visited;
static int[] result; 

public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	m = sc.nextInt();
	r = sc.nextInt();
	
	visited = new boolean[n+1];
	result  = new int[n+1]; // 배열 선언 시 0으로 초기화 
	
	// 1. 정점 수 만큼 그래프 초기
	for(int i=0; i<=n; i++) {
		graph.add(new ArrayList<Integer>());
	}
	
	// 2. 그래프에 간선 정보 저장 (양방향)
	for(int i=0; i<m; i++) {
		int start = sc.nextInt();
		int end = sc.nextInt();
		
		graph.get(start).add(end);
		graph.get(end).add(start);
	}
	
	// 깊이 우선 탐
	dfs(r);
	
	for(int i=1; i<=n; i++) {
		System.out.println(result[i]);
	}
}

static void dfs(int r) {
	visited[r] = true; // 방문 확인
	result[r]=cnt; // 방문 순서 저장
	cnt++;
	Collections.sort(graph.get(r)); // 인접 정점 오름차순 
    // Collections.sort(graph.get(r), Collections.reverseOrder()); // 24480. 내림차순
	for(Integer v : graph.get(r)) {
		if(!visited[v]) { // 인접 정점 중 방문하지 않은 노드 방문 
			dfs(v);
		}
	}
	return ; // 모두 방문했을 때 return 
	
}

 

 

24444, 24445. 알고리즘 수업 - 너비 우선 탐색 1, 2

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

마찬가지로, 정점의 방문 순서를 출력하는 문제이며 두 문제의 차이점은 인접 정점 방문 순서 뿐이다.

static int n, m, r;
static int cnt = 1;
static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
static boolean[] visited;
static int[] result; 

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	m = sc.nextInt();
	r = sc.nextInt();
	
	visited = new boolean[n+1];
	result = new int[n+1];
	
	// 그래프 노드 수 만큼 초기화 
	for(int i=0; i<=n; i++) {
		graph.add(new ArrayList<Integer>());
	}
	
	// 그래프 간선 정보 저장 (양방향) 
	for(int i=0; i<m; i++) {
		int start = sc.nextInt();
		int end = sc.nextInt();
		graph.get(start).add(end);
		graph.get(end).add(start);
	}
	
	for(int i=1; i<=n; i++) {
		Collections.sort(graph.get(i)); // 오름차순으로 인접 노드 방문
        // Collections.sort(graph.get(i), Collections.reverseOrder()); //  24445. 내림차순
	}
	
	bfs(r);
	
	for(int i=1; i<=n; i++) System.out.println(result[i]);
}

static void bfs(int r) {
	visited[r] = true;
	result[r] = cnt;
	cnt++;
	
	// Queue 자료형 활용 
	Queue<Integer> queue = new LinkedList<Integer>();
	queue.add(r);
    
	while(!queue.isEmpty()) {
		int now = queue.poll(); 
		
		// 해당 노드와 간선으로 연결된 모든 노드 탐색 
		for(Integer v: graph.get(now)) {
			// 선입선출로 특정 노드에 연결된 모든 노드 먼저 탐색 후 다음 노드(간선)로 이동 
			if(!visited[v])  {
				queue.add(v);
				visited[v] = true;
				result[v] = cnt;
				cnt++;
			}
		}
	}
}

 

 

1260. DFS와 BFS

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

위의 문제와 별 다를거 없지만, 위의 문제는 정점 번호 기준으로 방문 순서를 출력한다면 이번 문제는 방문한 순서대로 정점 번호를 출력한다. 

static int n, m, r;
static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
static boolean[] visited;

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	n = sc.nextInt();
	m = sc.nextInt();
	r = sc.nextInt();
	
	visited = new boolean[n+1];
	for(int i=0; i<=n; i++) {
		graph.add(new ArrayList<Integer>());
	}
	
	for(int i=0; i<m; i++) {
		int start = sc.nextInt();
		int end = sc.nextInt();
		graph.get(start).add(end);
		graph.get(end).add(start);
	}
	
	// 정점이 작은 것부터 방문 > 오름차순 
	for(int i=0; i<=n; i++) Collections.sort(graph.get(i));
	
	dfs(r);
	
	System.out.println();
	for(int i=0; i<=n; i++) visited[i]=false;
	
	bfs(r);	
}

static void dfs(int r) {
	System.out.print(r+" ");
	visited[r]=true;
	
	for(Integer v: graph.get(r)) {
		if(!visited[v]) {
			dfs(v);
		}
	}
	return;
}

static void bfs(int r) {
	System.out.print(r+" ");
	visited[r]=true;
	
	Queue<Integer> queue = new LinkedList<Integer>();
	queue.add(r);
	while(!queue.isEmpty()) {
		int now = queue.poll();
		for(Integer v : graph.get(now)) {
			if(!visited[v]) {
				System.out.print(v+" ");
				queue.add(v);
				visited[v]=true;
			}
		}
	}
}

위의 문제들과 다를건 없지만, DFS와 BFS 소스를 한눈에 볼 수 있어 자주 참고하는 소스코드

 

 

2178. 미로 탐색

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

그래프 탐색 문제 풀때 주로 DFS로 먼저 접근하였는데 이 문제는 DFS가 아닌 BFS로 접근해야 하는 문제였다. 특정 위치까지의 이동하는 최소 칸수를 구하는 문제이기 때문이다. 최단 거리 문제는 BFS로 풀어야한다!

그 이유는 성능이 더 좋다. BFS의 경우 종점에 도달하면 멈추지만 DFS는 모든 경우를 다 탐색하기 때문에 종점에 도달해 최단 경로가 나오더라도 계속 순회한다.

여튼 이 문제도 활용되는 문제가 많아서 자주 참고하는 답안이다.

static int n, m;
static int[][] arr;
static boolean[][] visited;

static int[][] idx = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

static class Node {
	int x, y;
	public Node(int x, int y) {
		this.x=x;
		this.y=y;
	}
}


public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt(); // row
	m = sc.nextInt(); // col
	
	visited = new boolean[n][m];
	arr = new int[n][m];
	
	for(int i=0; i<n; i++) {
		String[] s = sc.next().split("");
		for(int j=0; j<s.length; j++) {
			arr[i][j]=Integer.parseInt(s[j]);
		}
	 } 
	
	bfs(new Node(0, 0));

	System.out.println(arr[n-1][m-1]);
}


static void bfs(Node node) {
	visited[node.x][node.y]=true;
	
	Queue<Node> queue = new LinkedList<Node>();
	queue.add(node);
	
	while(!queue.isEmpty()) {
		Node now = queue.poll();
		for(int i=0; i<4; i++) {
			int dx = now.x+idx[i][0];
			int dy = now.y+idx[i][1];
			
			if(dx<n && dy<m && dx>=0 && dy>=0 && arr[dx][dy]==1 && !visited[dx][dy]) {
				visited[dx][dy] = true;
				queue.add(new Node(dx, dy));
				arr[dx][dy] = arr[now.x][now.y]+1; // 이동 거리 저장
			}
		}
	}
}

해당 답에서 중요한 부분은 이동한 칸 수(이동 거리)를 구하기 위해 배열을 순회하면서 +1씩 해주는 부분이다.

지금 있는 위치까지 이동 거리를 저장하기 위해 마지막에 도달하기까지 +1씩 더해준다. 이렇게 하다보면 마지막에 최단 거리를 구할 수 있다.

 

 

1697. 숨바꼭질

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

조금 해맸지만, 그래프 순회 낮은 난이도부터 풀다보니 전보다는 쉽게 풀 수 있었던 문제. 바로 전 문제인 미로탐색(2178) 풀이를 활용하였다.

내가 참고한 블로그 https://smartpro.tistory.com/18

[백준/1697/Java] 숨바꼭질 - BFS 풀이

나도 설명 기깔나게 쓰고싶지만 밀린 포스팅과 피곤 이슈로 위의 블로그로 대체..

static int result=0;
static int[] arr;
static int n, k;

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	n = sc.nextInt();
	k = sc.nextInt();
	
	// ** new int[100000] 런타임에러(ArrayIndxOutLOfBounds)
	arr = new int[100001];
	
	bfs(n);
	System.out.println(arr[k]-1);
}

static void bfs(int x) {
	arr[x]++;
	
	Queue<Integer> queue = new LinkedList<Integer>();
	queue.add(x);
	
	while(!queue.isEmpty()) {
		int now = queue.poll();
		
		if(now==k) break;
		
		// +1
		if(now+1<=100000 && arr[now+1]==0) { // **
			queue.add(now+1);
			arr[now+1] = arr[now]+1;
		}
		// -1
		if(now-1>=0 && arr[now-1]==0) {	
			queue.add(now-1);
			arr[now-1] = arr[now]+1;
		}
		// *2
		if(now*2<=100000 && arr[now*2]==0) {
			queue.add(now*2);
			arr[now*2] = arr[now]+1;
		}
		
	}
}

• 일직선상에서 수빈이가 이동할 수 있는 방법은 앞으로 한칸, 뒤로 한칸, 현재 위치의 2배 뿐으로 순회를 도는 경우는 +1, -1, *2 3가지이다.
• 배열 초기화 시 크기를 주어진 N과 K 범위에 따라 100,000으로 하였는데 그럼 런타임에러가 난다. 아무래도 N, K(수빈이와 동생의 위치)가 100,000까지 포함되어서 100,001 까지 초기화 시켜줘야되는 듯 하다.
• 두 번째로 오류난 포인트는 ** 부분이다. 처음에 now-1>=1 이라고 지정했는데 그럼 '틀렸습니다!' 결과를 받게된다. now-1>=0 라고 해야 통과다. 이 또한 마찬가지로 N, K의 범위가 >=0, <=100,000임을 기억하자!

 

다른 문제들이 있지만.. 추후 추가할 예정..