[JAVA] 1743번 - 음식물 피하기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

딱 보자마자 저번에 풀었던 배추문제랑 똑같다고 생각했다.

DFS/BFS를 이용해서 주위에 인접한 애들을 하나의 묶음으로 생각하고 각 묶음중에서 제일 큰 값을 정답으로 출력하면된다!

이차원배열이기 때문에 인접행렬을 이용했다! 

 

시간복잡도

O(N*M)이다 O(10,000) 로 시간내에 충분히 가능하다 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 이차원 배열을 만들고 음식물을 입력받아서 완성한다

2. DFS를 수행하고, 최댓값을 비교하면서 찾는다

3. 정답(최댓값) 을 출력한다.

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

1회차 시도

=> 알고리즘 상 오류는 없는데 정답이 제대로 출력이 되지 않았다.

원인: 배열의 범위지정 문제였다! 

for(int i=0; i<k; i++) {
        	st = new StringTokenizer(br.readLine());
        	int x = Integer.parseInt(st.nextToken())-1;
        	int y = Integer.parseInt(st.nextToken())-1;
        	adjMatrix[x][y] = 1;
        }

이렇게 음식물 좌표를 입력받을때 1씩 빼야한다. 그래서 문제에서도 좌표에 음식물 그림이 그려져있었군

왜냐면 이 문제는 (0,0)이 시작이 아니라 (1,1)이 시작이다! 근데 배열은 0부터 시작이니까 1,1 로 입력받아도 좌표에는 0,0좌표에 넣어야한다!

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n,m,k,cnt;
	static int[][] adjMatrix;
	static boolean[][]  isVisited;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,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());
    	
        isVisited = new boolean[n][m];
        adjMatrix = new int[n][m];
        
        //음식물 좌표 입력 받기 
        for(int i=0; i<k; i++) {
        	st = new StringTokenizer(br.readLine());
        	int x = Integer.parseInt(st.nextToken())-1;
        	int y = Integer.parseInt(st.nextToken())-1;
        	adjMatrix[x][y] = 1;
        }
        
        int ans = 0;
        for(int i=0; i<n; i++) {
        	for(int j=0; j<m; j++) {
        		if(adjMatrix[i][j] == 1 && !isVisited[i][j]) {
        			cnt = 0;
        			dfs(i,j);
        			ans = Math.max(ans, cnt);
        			
        		}
        	}
        }
        
        System.out.println(ans);
        
    }

	private static void dfs(int x, int y) {
		isVisited[x][y] = true;
		cnt++; //현재 위치 포함 
		
		for(int l=0; l<4; l++) {
			int nx = x+dx[l];
			int ny = y+dy[l];
			
			if(nx>=0 && ny>=0 && nx<n && ny<m) {
				if(adjMatrix[nx][ny]==1 && !isVisited[nx][ny]) {
					dfs(nx,ny);
					
				}
			}
		}
		
	}

	

}