인프런 커뮤니티 질문&답변

안녕하세요 360님 ㅎㅎ

이 백조의 호수 문제는 시간초과가 깐깐하기로 유명한 문제입니다.

그러니 효율의 효율을 생각해야 하는데요.

	while(true){
		cnt++;
		for(int i=0;i<y;i++){
			for(int j=0;j<x;j++){
				if(arr[i][j]==-1){
					for(int k=0;k<4;k++){
						int ny=i+dy[k];
						int nx=j+dx[k];
						if(ny<0||ny>=y||nx<0||nx>=x)continue;
						if(arr[ny][nx]==cnt)arr[i][j]=cnt+1;
					}
				}
			}
		}
		dfs(v[0].first,v[0].second);

360님의 코드를 잠깐 볼까요?

360님의 메인 로직은 다음과같습니다.

1.물이라면 >> 4방향을 체크해서 얼음이라면 cnt를 기반으로 녹임을 구현한다.

2.그리고 나서 dfs를 돌린다. - 시작지점부터.

이 2가지의 로직은 조금은 비효율적입니다.

1. 만약 녹인 지점부터 다시 탐색을 이어나간다면 굳이 맵전체를 매번 탐색할 필요는 없습니다.

2. 계속해서 시작지점부터 dfs가 아닌 녹인 지점부터 bfs 또는 dfs를 돌려야 더 효율적입니다.

그림으로 설명하자면 다음과 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴이에요.

주어진 문제를 푸는 방법은 크게 2가지가 있습니다. 첫 번째는 모든 경우를 탐색하는 완전 탐색 방법이고, 두 번째는 중복을 허용하지 않는 조합을 구하는 방법입니다. 여기서는 후자의 방법을 사용하시는 것 같아요.

주어진 코드를 보면서 시간 복잡도를 분석해보면, 중복 조합을 구하는 이중 반복문을 사용하고 있습니다. 이 방법은 모든 경우를 구하므로, 시간 복잡도가 O(N^k)로 매우 커집니다. 따라서 큰 입력에 대해선 시간 초과가 발생할 수 있어요.

이 문제를 해결하기 위해서는 백트래킹 알고리즘을 이용하여 중복 조합을 찾는 방법을 바꿔주어야 합니다. 구체적인 구현 방법은 아래 링크에 자세히 설명되어 있으니 참고해보세요!

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

코드의 수정이 어렵다면, 위 링크에 있는 코드를 참고하시는 것도 좋아요.

자세한 답변이 되지 않아 죄송해요. 제가 도움을 드리길 바랍니다. 감사합니다.