[코딩테스트] 백준(BAEKJOON) - 빙산(JAVA)

안녕하세요~

또 오랜만에 코딩테스트 관련 글을 올려볼까합니다.

 

요즘 JPA쪽을 공부해보느라 정신이 없네요. ㅠㅠㅠ

 

어렵네요 참~

 

이번 문제도 어렵네요 하하~🤣🤣

그저 열심히하면 언젠가는 기회가 있겠지라는 마음으로 오늘 하루도 버텨보고 있습니다!

 

오늘 풀어볼 문제 정답률이 25%밖에 되지 않네요

바로 문제 만나보시죠~

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

2573번: 빙산

그렇습니다 한 회차에 따라 빙산이 줄어들고 줄어든 빙산이 두 덩어리 이상으로 분리되는 최초의 시간을 구하는 문제 되겠습니다~

 

이제 제 풀이와 함께 간단한 설명을 남겨보겠습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

	

public class Main {
	static ArrayList<ArrayList<Integer>> arr=new ArrayList<>();
	static ArrayList<ArrayList<Integer>> temp;
	static boolean[][] visited;
	
	static int[] xm= {-1,0,0,1};
	static int[] ym= {0,-1,1,0};
	
	static int m;
	static int n;
	static int cnt;
	static int answer;
	static boolean zerochecker;
	
	public static void main(String[] args) throws IOException  {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		cnt=0;
		answer=0;
		zerochecker=false;
		
		String line="";
		line=bf.readLine();
		
		st=new StringTokenizer(line);
		
		m=Integer.parseInt(st.nextToken());
		n=Integer.parseInt(st.nextToken());
		
		for(int i=0;i<m;i++)
		{
			
			line=bf.readLine();
			st=new StringTokenizer(line);
			ArrayList<Integer> rowList=new ArrayList<>();
			
			for(int j=0;j<n;j++)
			{
				rowList.add(Integer.parseInt(st.nextToken()));
			}
			arr.add(rowList);
			
		}
		
		int x_=-1;
		int y_=-1;
		
		while(true)
		{
			answer++;
			visited=new boolean[m+1][n+1];

			temp=new ArrayList<>();
            zerochecker=false;
			for(int i=0;i<m;i++)
			{
				
				ArrayList<Integer> tempList=new ArrayList<>();
				for(int j=0;j<n;j++)
				{
					int zc=0;
                    if(arr.get(i).get(j)!=0)
                        zerochecker=true;

					for(int k=0;k<4;k++)
					{

						x_=i+xm[k];
						y_=j+ym[k];
						
						if(x_>=0&&x_<m&&y_>=0&&y_<n)
						{
							if(arr.get(x_).get(y_)==0)
								zc++;
						}

					}
					
					if(arr.get(i).get(j)-zc>0)
					{
						tempList.add(arr.get(i).get(j)-zc);
					}
						
					else
					{
						tempList.add(0);
					}
						
				}
				temp.add(tempList);
				
			}
			
			
			if(!zerochecker)
			{
				System.out.println("0");
				return;
			} 
			
			for(int i=1;i<m;i++)
			{
				for(int j=1;j<n;j++)
				{
					if(!visited[i][j]&&temp.get(i).get(j)>0)
					{
						visited[i][j]=true;
						cnt++;
						dfs(i,j);
					}
				}
			}
			
			if(cnt>=2)
				break;
			else
			{
				cnt=0;
				arr=(ArrayList<ArrayList<Integer>>) temp.clone();
				temp=null;
			}
				
		}
		
		System.out.println(answer);

		
		
	}
	static void dfs(int x, int y)
	{
		for(int i=0;i<4;i++)
		{
			int x_=x+xm[i];
			int y_=y+ym[i];
			
			if(x_>=0&&x_<m&&y_>=0&&y<n)
			{
				if(!visited[x_][y_]&&temp.get(x_).get(y_)>0)
				{
					visited[x_][y_]=true;
					dfs(x_,y_);
				}
			}
		}
	}

}

중간중간 수정하며 풀어 주석처리가 많아 지우다보니 정상 코드도 지워지지 않았나 걱정이 되네용

설명 시작하겠습니다.

 

		for(int i=0;i<m;i++)
		{
			
			line=bf.readLine();
			st=new StringTokenizer(line);
			ArrayList<Integer> rowList=new ArrayList<>();
			
			for(int j=0;j<n;j++)
			{
				rowList.add(Integer.parseInt(st.nextToken()));
			}
			arr.add(rowList);		
		}

- 이 부분은 기존에 2차 배열을 사용해 구현했으나 속도 문제가 있을까 싶어서 이렇게 ArrayList로 변경 후 구현했습니다.

 

- 다음은 While(true)부분입니다.

			for(int i=0;i<m;i++)
			{
				
				ArrayList<Integer> tempList=new ArrayList<>();
				for(int j=0;j<n;j++)
				{
					int zc=0;
                    if(arr.get(i).get(j)!=0)
                        zerochecker=true;

					for(int k=0;k<4;k++)
					{

						x_=i+xm[k];
						y_=j+ym[k];
						
						if(x_>=0&&x_<m&&y_>=0&&y_<n)
						{
							if(arr.get(x_).get(y_)==0)
								zc++;
						}

					}
					
					if(arr.get(i).get(j)-zc>0)
					{
						tempList.add(arr.get(i).get(j)-zc);
					}
						
					else
					{
						tempList.add(0);
					}
						
				}
				temp.add(tempList);

- 다음은 전체 빙산을 순회하면서 녹은 부분을 찾아내는 로직입니다.

- 그렇기에 x축인 m, y축인 n만큼 반복문을 돌면서 위, 아래, 양 옆에 있는 0을 찾습니다.

- 찾은 0의 갯수를 zc변수에 저장해놨다가 만약 현재 arr(i,j)- zc의 값이 0보다 크다면 그대로 적용 0보다 작다면 0으로 세팅해줍니다.

 

-그리고 해당 내용들을 현재의 arr 이 아닌 temp를 만들어 적용합니다.

- 이 문제의 핵심이 아닐까 생각이 드네요. 기존의 array를 재활용하는게 아닌 tempList에 새판을 짜서 값을 적용시켜야 합니다.

적용된 tempList는 추후 다시 1년이 지난 빙산의 역할을 해줄 예정입니다.

 

 

			if(!zerochecker)
			{
				System.out.println("0");
				return;
			}

zerochecker는 이제 더이상 녹을 빙산이 없는지 확인용으로 사용합니다.

 

			for(int i=1;i<m;i++)
			{
				for(int j=1;j<n;j++)
				{
					if(!visited[i][j]&&temp.get(i).get(j)>0)
					{
						visited[i][j]=true;
						cnt++;
						dfs(i,j);
					}
				}
			}
			
			if(cnt>=2)
				break;
			else
			{
				cnt=0;
				arr=(ArrayList<ArrayList<Integer>>) temp.clone();
				temp=null;
			}

해당 부분은

이제 빙산 구역을 찾는 dfs를 실행합니다.

빙산값이 0보다 크다면 녹지 않았다는 뜻으로 방문 처리 후 dfs를 실행합니다.

 

만약 cnt즉 빙산 구역이 2이상이라면 문제의 조건을 만족하니 break합니다.

그렇지 않다면 다시 녹은 빙산(temp)를 기준으로 arr에 복사해 반복합니다.

 

어떠신가요?

 

저는 하나하나 풀어보면 쉬운듯했지만 clone때문에 고생좀 했습니다. clone을 몰라서 계속 빙산 녹은게 이상하게 적용됐었습니다. 이 글을 쓰는데 이래저래 걸려 2주나 걸렸네요.

 

감사합니다😊😊😊😊