[백준] 1743번 음식물 피하기 - Java

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 123528KB | 시간 580ms | 코드 길이 1949B

import java.io.*;
import java.util.*;

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int k;
	private static boolean[] visited = new boolean[k];
	private static int[][] trash = new int[k][2];
	private static int[][] trash_node = new int[k][k];
	
	private static int cnt;
	
	private static PriorityQueue<Integer> graph = new PriorityQueue<>();
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		trash = new int[k][2];
		trash_node = new int[k][k];
		visited = new boolean[k];
		
		for(int i = 0 ; i < k ; i++) {
			StringTokenizer st_trash = new StringTokenizer(bf.readLine());
			int x = Integer.parseInt(st_trash.nextToken());
			int y = Integer.parseInt(st_trash.nextToken());
			trash[i][0] = x;
			trash[i][1] = y;
			for(int j = 0 ; j < i ; j++) {
				if(Math.abs(trash[j][0] - trash[i][0]) == 1 && trash[j][1] - trash[i][1] == 0) {
					trash_node[i][j] = 1;
					trash_node[j][i] = 1;
				} else if(Math.abs(trash[j][1] - trash[i][1]) == 1 && trash[j][0] - trash[i][0] == 0) {
					trash_node[i][j] = 1;
					trash_node[j][i] = 1;
				}
			}
		}
		cnt = 0;
		
		int max = 0;
		//시작 노드를 정하는 for문
		for(int i = 0 ; i < k ; i++) {
			cnt = 0;
			if(!visited[i]) {
				bfs(i);
				if(max <= cnt) {
					max = cnt;
				}
			}
		}
		
		bw.write(Integer.toString(max));
		
		bw.flush();
		bf.close();
		bw.close();
	}
	
	private static void bfs(int node) {
		visited[node] = true;
		graph.remove(node);
		cnt ++;
		for(int i = 0 ; i < k ; i++) {
			if(!visited[i] && trash_node[node][i] == 1) {
				graph.add(i);
				bfs(i);
			}
		}
	}
}

 

보통 그래프 탐색할 때 노드를 보는 것 처럼 봐야합니다.

이게 무슨 말이냐면 (3, 4)를 0번째 노드로 , (2, 2)를 1번째 노드로 ... 보는 식으로 봐야한다는 말입니다. 그리고 노드를 이용해서 그래프 탐색을 하여 연결된 노드의 개수를 세는 방식으로 갑니다.

 

첫번째로 해야할 일은 노드를 연결해야합니다. 

for(int i = 0 ; i < k ; i++) {
			StringTokenizer st_trash = new StringTokenizer(bf.readLine());
			int x = Integer.parseInt(st_trash.nextToken());
			int y = Integer.parseInt(st_trash.nextToken());
			trash[i][0] = x;
			trash[i][1] = y;
			for(int j = 0 ; j < i ; j++) {
				if(Math.abs(trash[j][0] - trash[i][0]) == 1 && trash[j][1] - trash[i][1] == 0) {
					trash_node[i][j] = 1;
					trash_node[j][i] = 1;
				} else if(Math.abs(trash[j][1] - trash[i][1]) == 1 && trash[j][0] - trash[i][0] == 0) {
					trash_node[i][j] = 1;
					trash_node[j][i] = 1;
				}
			}
		}

입력받은 데이터는 trash 배열에 들어갑니다. 그리고 방금 입력받은 데이터와 trash 배열에 있는 데이터를 가로 혹은 세로중 하나만 1차이가 나고 같다면 노드를 연결시켜줍니다.

 

그 뒤는 일반적인 bfs 코드입니다.

int max = 0;
		//시작 노드를 정하는 for문
		for(int i = 0 ; i < k ; i++) {
			cnt = 0;
			if(!visited[i]) {
				bfs(i);
				if(max <= cnt) {
					max = cnt;
				}
			}
		}

시작 노드를 정하는 코드는 main함수에 적고, (visited 배열을 확인하여 시작노드를 찾습니다.)

 

private static void bfs(int node) {
		visited[node] = true;
		graph.remove(node);
		cnt ++;
		for(int i = 0 ; i < k ; i++) {
			if(!visited[i] && trash_node[node][i] == 1) {
				graph.add(i);
				bfs(i);
			}
		}
	}

bfs 함수는 이렇게 만들었습니다.

---

후기

1트만에 성공해서 도서관에서 비명지를 뻔 봤습니다.

bfs 쓰는 건 지난 1학기 자료구조의 자료를 참고해서 써봤는데 이론이 실제 세계(?)에서 먹히(?)니까 더 벅차오르네요.

dfs로도 해봐야겠어요.