SLENDER ANKLES's 개발블로그

dfs의 진입점이 몇 번 나오냐를 판별하는 문제이다. 루프를 돌면서 dfs를 수행하면서 방문 기록을 갱신해준다. 

그러면 2차원 배열을 순회하면서 뭉터기 뭉터기를 판별 할 수 있게 된다. 

안전영역과 비슷하다고 할 수 있겠다.

1번의 실패를 했는데 그 것은 테스트케이스가 배열의 시작을 0,0으로 나와있다. 

4방향 검사를 원할히 하기 위해서 1,1부터 입력을 받고 있으므로 

주어진 테스트케이스에 x+1, y+1을 해주면 된다. 

중요한 부분은

- 치즈로 둘러 싸여 있는 내부의 0인 부분은 바깥 공기가 아니라는 점이다.

- 치즈의 한 면이라도 공기와 접촉되면 한 시간 후에 없어진다.

1) 0,0에서 시작해서 공기에 해당하는 부분을 3(공기영역을 3으로 표기하게끔 해주었음)으로 갱신해주는 dfs를 수행한다.

2) 그리고 공기와 접촉되는 부분의 치즈를 0으로 바꾸어준다. 치즈의 개수를 세어준다.

루프를 수행하는 횟수를 시간과 연결시켜 답을 구한다.

공기와 맞닥뜨린 치즈의 개수를 세면서 전체 치즈의 개수를 세어 갱신하며 마지막 한 시간 전의 남아있는 치즈 개수를 구할 수 있게 유도

* 보물섬 안에서 가장 길이가 긴 육지의 두 공간에 보물이 묻혀있다.

* 보물섬 안에서 반복문을 순회하며 'L', 즉 육지인 곳이 나타나면 거기서부터 bfs를 수행해 가장 거리가 긴 것을 찾았다. 

* 가장 거리가 긴 육지사이의 거리가 결국 보물이 숨겨져 있는 두 육지안의 지점까지의 거리를 의미하니까.

* 4방향 검사가 아니라 대각선까지 고려하는 8방향검사를 수행한다.

* 루프를 돌면서 dfs를 진입하는 개수가 결국 섬의 개수다.

* 각 테스트 케이스마다 섬의 개수를 출력한다.

* 기존의 처음 테스트케이스의 개수가 주어지는 형태가 아니라 입력값이 0, 0이면 끝나게 끔 

하는 부분에서 한 번 틀렸지만 이런문제도 있다 정도로 생각하였음

도저히 제출이 성공하지 않는다.??

- 하루에 한 개씩 밖에 익지않는다는 점을 주의하라. 라는 도움말을 보았다. 

다음에 이 것을 고려해서 다시 한 번 작성해보아야 겠다.

dfs를 돌릴 때 특정 사각형 밖의 영역을 구하는 문제 였다. 

- 문제점은 dfs의 4방향 처리 때 끝에서 바깥부분을 검사할 때 발생했다.

- 예외처리를 거의 날로 한 거 같다.

- 풀기는 풀었지만 제 정신이 아니었다. 

- 바깥 부분을 -1로 다 만들어 놓았다면 이렇게 코드가 난잡해지지 않을 것 같다. 

- 다시 풀어봐야 한다.

- 소트는 버블 소트를 사용한다. 

- stl에서 제공해주는 소트를 사용하여서도 구현해보아야겠다.

그래프의 첫번째 노드에서 출발해서 연결된 서로 연결된 노드들은 모두 감염된다. 

첫 번째 노드가 속하지 않는 그래프에는 감염되지 않는다. 

그렇다면 첫번째 노드가 속한 그룹의 개수를 세면 감염되는 컴퓨터의 수를 알 수 있게 된다. 

인덱스 위치를 앞 뒤로 주고 문제의 규칙에 맞게 인덱스를 옮겨다니며 값을 갱신하고 출력해주는 형식으로 

답을 출력하였다.

front_index, end_index를 이동시켰다. 

규칙

while(front_index != end_index){

1. front_index에서 출력하고 front_index++

2. front_index의 값을 end_index++ 위치에 갱신

3. front_index++해준다.

}

이 조건을 수행해주니까 답이 도출

gcd는 

예를 들어 

8, 28의 최대 공약수를 구해보면

3 = 28 / 8 ...4

2 = 8 / 4 ...0

AB/GCD = GCD*a*b;

결국 AB/GCD는 최소공배수가 된다

[다시 풀었어도 난해한 문제]

오랜만에 드디어 문제가 풀렸다. ㅜㅜ

답이 잘 안 나오는 문제가 너무 많다. 분발하자. 

떡 먹는 호랑이 문제는 내가 너무 어렵게 생각한 거 같다. 

알고 봤더니 쉽고 정말 좋은 문제였다.라고 스스로 평가하고 싶다. 

우선 첫날 준 떡 + 두번째 날 준 떡 = 세번째 날 준떡 이어야 한다는 것은 피보나치 점화식을 가진다는 것을 알 수 있음!

문제에서는 n번째 날에 k의 떡을 준 것을 토대로 문제를 풀어 첫 번째 날과 두 번째 날에 준 떡의 개수를 알아내야 한다. 

처음은 점화식의

f(n) = a*f(n-2) + b*f(n-1) 이라는 식을 세워서 계수를 알아내야 한다고 생각 한다. 물론 맞다.

a와 b를 빼놓고 생각해본다면

f(n) = f(n-2) + f(n-1)이라는 점화식이 나오고

f(1) = 1, f(2) = 1로 놓으면 계수가 나오지 않겠는가!!!

결국 첫날 준 떡 a , 두번째 날 준 떡 b의 계수를 구할 수 있게 된다. 

이 계수를 토대로 a와 b를 구해야 한다. 어떻게?

처음은 다이나믹 프로그래밍으로 풀어야 하나를 생각해보면서 이상한 고민을 했었다. 

하지만 단지 이중 for문을 돌면서 때려 맞추고 break으로 빠져나오면 된다.

심각한 루프를 돌지도 않고 또한 워낙 범위가 많지 않아 무리 없이 수행 할 수 있다.!!!

문제의 조건들을 면밀히 살펴 시간분석도를 대략적으로 계산할 줄 알아야 한다는 생각을 했다. 이 부분을  좀 더 공부해야겠다.