[BOJ]19236번: 청소년 상어

 

www.acmicpc.net/problem/19236

---

시뮬레이션 문제입니다.

 

어떻게 움직여야하는 지는 문제 꼼꼼히 읽어보면 아실테니

그것보다는 푸시면서 신경써야할 예외케이스에 대해 말하겠습니다.

 

1. DFS로 푸시든 BFS로 푸시든 매 상태의 2차원 그래프는 서로 분리되어 있어야 합니다.

그냥 매 깊이 갈 때 마다 copy를 하시든, 아니면 가공하고 다시 원상복귀를 하시든

매 상태는 구분되어야 합니다.

즉 탐색하고 빠져나오면 다시 원래 상태에서 다음 탐색을 시작해야된다는 의미입니다.

이게 머릿속에서 꼬이시면 시뮬레이션은 답이 없습니다.

 

2. 물고기들이 이동하는 시점을 처리할 때 각 물고기는 한 번만 이동해야 합니다.

저 같은 경우는 그냥 2차원 배열 다 뒤지면서 숫자 작은 것부터 이동시켰는데요.

//BAD case

for (int num = 1; num <= 16; ++num)
{		
	for (int i = 0; i < MAP_SIZE; ++i)
	{
		for (int j = 0; j < MAP_SIZE; ++j)
		{
			if (map[i][j].num == num)
			{
			}
		}
	}
}

 

이 때 이동 여부를 표시하는 bool isChanged 같은 플래그가 없다면 문제가 될 수 있습니다.

 

예를 들어, 1번 물고기가 (1,1)에 있다가 (2,2)로 간 경우,

제가 푼 방식으로는 2차원 배열을 다 뒤지기 때문에 (1,1) 갔다가 나중에 (2,2)가서

숫자가 1인 물고기가 또 있으니 얘가 또 움직이도록 할 것입니다.

이런 식으로 자신이 푼 방식에 대해 문제점을 빨리 캐치하셔야 합니다.

//GOOD case

for (int num = 1; num <= 16; ++num)
{		
	boolean isChanged = false;
	
	for (int i = 0; i < MAP_SIZE; ++i)
	{
		for (int j = 0; j < MAP_SIZE; ++j)
		{
			if (map[i][j].num == num && isChanged == false)
			{
				isChanged == true;
			}
		}
	}
}

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ19236.cc