백준_1743 음식물 피하기(자바) / DFS & BFS

시간 & 메모리 제한

문제

사방탐색을 문제에 주셔야죠,,,, 힌트에서 줬네요;

입력 & 출력

DFS를 이용한 문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Back_1743 {
	static int N,M,K,ans,temp;
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	static boolean[][] map;
	static boolean[][] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new boolean[N][M];
		visited = new boolean[N][M];
		
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			map[r-1][c-1]=true;
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(!visited[i][j] && map[i][j]) {
					temp=0;
					dfs(i,j);
					ans = Math.max(ans, temp);
				}
			}
		}
		System.out.println(ans);
		
	}

	private static void dfs(int x, int y) {
		temp++;
		visited[x][y]=true;
		for (int k = 0; k < 4; k++) {
			int xx = x+dx[k];
			int yy = y+dy[k];
			
			if(xx<0 || yy<0 || xx>=N || yy>=M)continue;
			if(!visited[xx][yy]&& map[xx][yy]) {
				dfs(xx,yy);
			}
		}
	}
}

- DFS와 BFS를 써본지 좀 된거 같아서 쉬운 문제를 이용해 풀이를 진행했습니다.

 

- 첫번째 풀이는 DFS를 이용한 문제풀이입니다. 이중 for문을 돌려서 먼저 음식물 쓰레기의 위치를 찾습니다.

 

- 그리고 음식물 쓰레기의 위치에서 사방탐색을 진행해, 쓰레기의 크기를 구해줍니다.

 

- BFS 역시 같은 원리로 풀이를 진행했습니다.

 

BFS를 이용한 문제풀이

package com.Back;

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

public class Back_1743 {
	static int N,M,K,ans,cnt;
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	static boolean[][] map;
	static boolean[][] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new boolean[N][M];
		visited = new boolean[N][M];
		
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			map[r-1][c-1]=true;
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(!visited[i][j] && map[i][j]) {
					cnt=0;
					bfs(i,j);
					ans = Math.max(ans, cnt);
				}
			}
		}
		System.out.println(ans);
		
	}

	private static void bfs(int x, int y) {
		Queue<point> q = new LinkedList<>();
		q.add(new point(x, y));
		visited[x][y] = true;
		cnt++;
		while(!q.isEmpty()) {
			point temp = q.poll();
			
			for (int k = 0; k < 4; k++) {
				int xx = temp.x +dx[k];
				int yy = temp.y +dy[k];
				if(xx<0 || yy<0 || xx>=N || yy>=M)continue;
				if(!visited[xx][yy] && map[xx][yy]) {
					q.add(new point(xx, yy));
					visited[xx][yy]=true;
					cnt++;
				}
			}
		}
	}

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

 

- BFS 역시 비슷한 풀이로 진행을 했습니다.

 

- 크게 다른점이 있다면 좌표를 담을 클래스를 만들어서 진행을 했습니다.