백준 1743번
https://www.acmicpc.net/problem/1743
코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.
이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.
통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.
선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.
좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.
첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.
최근에 DFS/BFS 문제만 풀어서 그런건지
그냥 그런건지 모르겠지만, 진짜 쉬운 문제였다.
DFS는 재귀함수를 통해 구현했다.
main문에서 전체를 탐색해서 map
에 1이면서 방문하지 않는 조건에 걸리는
좌표값으로 DFS 재귀함수를 실행한다.
재귀함수를 실행 후 재귀되는 횟수만큼 count
값을 증가 해주면 결국 1이 붙어있는 갯수가 되니까
Math.max(max, count)
의 count
값이 정답이 된다.
BFS는 Queue를 이용해서 구현했다.
BFS도 마찬가지로 main문에서 전체를 탐색해서 map
에 1이면서 방문하지 않는 조건에 걸리는 좌표값으로 BFS 재귀함수를 실행한다.
while( !que.isEmpty() )
의 조건 반복을 통해서 인접한 1은 모두 count
가 증가하게 되고
마지막에 나오는 count
값이 인접한 1의 갯수가 된다.
Math.max(max, count)
의 count
값이 정답이 된다.
DFS/BFS 척척박사 되고싶다..
import java.util.*; import java.io.*; public class Main { static boolean visit[][]; static int map[][]; static int dirX[] = {0, 0, -1, 1}; static int dirY[] = {-1, 1, 0, 0}; static int N, M; static int nowX, nowY; static int x, y; static int count = 1; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()) + 1; M = Integer.parseInt(st.nextToken()) + 1; int K = Integer.parseInt(st.nextToken()); map = new int[N][M]; visit = new boolean[N][M]; for(int i=0; i<K; i++) { st = new StringTokenizer(br.readLine()); y = Integer.parseInt(st.nextToken()); x = Integer.parseInt(st.nextToken()); map[y][x] = 1; } // 1을 만나면 탐색 시작 int max = Integer.MIN_VALUE; for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { count = 0; if(visit[i][j] == false && map[i][j] > 0) { DFS(j, i); max = Math.max(max, count); } } } System.out.println(max); } static void DFS(int x, int y) { visit[y][x] = true; count++; for(int i=0; i<4; i++) { nowX = x + dirX[i]; nowY = y + dirY[i]; if(Range_check() && visit[nowY][nowX] == false && map[nowY][nowX] > 0) { DFS(nowX, nowY); } } } // End of DFS static boolean Range_check() { return (nowX >= 0 && nowY >= 0 && nowX < M && nowY < N); } } // End of class
import java.util.*; import java.io.*; public class Main { static boolean visit[][]; static int map[][]; static int dirX[] = {0, 0, -1, 1}; static int dirY[] = {-1, 1, 0, 0}; static Queue<Node> que = new LinkedList<>(); static int N, M; static int nowX, nowY; static int x, y; static int count; static class Node { int x; int y; public Node(int x, int y) { this.x = x; this.y = y; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()) + 1; M = Integer.parseInt(st.nextToken()) + 1; int K = Integer.parseInt(st.nextToken()); map = new int[N][M]; visit = new boolean[N][M]; for(int i=0; i<K; i++) { st = new StringTokenizer(br.readLine()); y = Integer.parseInt(st.nextToken()); x = Integer.parseInt(st.nextToken()); map[y][x] = 1; } int max = Integer.MIN_VALUE; for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { count = 1; if(visit[i][j] == false && map[i][j] > 0) { BFS(j, i); max = Math.max(max, count); } } } System.out.println(max); } static void BFS(int x, int y) { que.offer(new Node(x, y)); visit[y][x] = true; while( !que.isEmpty() ) { Node node = que.poll(); for(int i=0; i<4; i++) { nowY = node.y + dirY[i]; nowX = node.x + dirX[i]; if(Range_check() && visit[nowY][nowX] == false && map[nowY][nowX] == 1) { que.offer(new Node(nowX, nowY)); visit[nowY][nowX] = true; count ++; } } } } // End of BFS static boolean Range_check() { return (nowX >= 0 && nowY >= 0 && nowX < M && nowY < N); } } // End of class