39. 1743번 음식물 피하기

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

1743번: 음식물 피하기

바로 이전 포스팅한 문제와 동일한 문제

차이점은 전문제는 하나하나 지정해주어 입력했다면

이번엔 좌표를 입력해 설정해준다는 것

 

DFS로 풀었다

 

1. 입력부분

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 int[n+1][m+1];
		visited = new boolean[n+1][m+1];
		
		
		for (int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			map[x][y] =1;
		}
		
		for(int i=0; i<n; i++){
			for(int j=0; j<4; j++){
				if (!visited[i][j] && map[i][j]==1){
					int temp = cnt;
					cnt = 0;
					dfs(i,j);
					cnt = Math.max(cnt,temp);
				}
			}
		}
		
		System.out.println(cnt);

		
	}

 

2. 탐색부분

private static void dfs(int x, int y) {
		
		//처음 방문하는곳 방문처리, 개수+1
		visited[x][y] = true;
		cnt++;
		
		for (int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			//범위 넘어가면 넘기기
			if (nx < 0 || ny < 0 || nx > n || ny > m) {
				continue;
			}
			
			//방문x, 1이면 방문처리 후 주변 탐색
			if (!visited[nx][ny] && map[nx][ny] == 1) {
				visited[nx][ny] = true;
				dfs(nx, ny);
			}
			
		}
		
	}

 

 

코드전문

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

public class training4 {
	private static int n,m,k;
	private static int[][] map;
	private static boolean[][] visited;
	private static int cnt;
	private static int[] dx = {0, 1, 0, -1};
	private static int[] dy = {1, 0, -1, 0};
	
	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 int[n+1][m+1];
		visited = new boolean[n+1][m+1];
		
		
		for (int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			map[x][y] =1;
		}
		
		for(int i=0; i<n; i++){
			for(int j=0; j<4; j++){
				if (!visited[i][j] && map[i][j]==1){
					int temp = cnt;
					cnt = 0;
					dfs(i,j);
					cnt = Math.max(cnt,temp);
				}
			}
		}
		
		System.out.println(cnt);

		
	}

	private static void dfs(int x, int y) {
		
		//처음 방문하는곳 방문처리, 개수+1
		visited[x][y] = true;
		cnt++;
		
		for (int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			//범위 넘어가면 넘기기
			if (nx < 0 || ny < 0 || nx > n || ny > m) {
				continue;
			}
			
			//방문x, 1이면 방문처리 후 주변 탐색
			if (!visited[nx][ny] && map[nx][ny] == 1) {
				visited[nx][ny] = true;
				dfs(nx, ny);
			}
			
		}
		
	}
}

 

결과