Red Salmon

출처 : https://www.acmicpc.net/problem/2146

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2146.cpp

문제가 상당히 귀찮다. 어려운건 아니지만 상당히 귀찮고 오직 BFS로는 풀 수있으나 오직 DFS로는 풀 수가 없다. 아마 있긴할텐데 엄청 복잡해질거다. 나는 DFS+BFS로 풀었다.

문제는 어떤 섬에서 섬까지 다리를 놓을때 최소한이 되는 값이다. 이는 결국 하나씩 다 해봐야 알 수 있는 것이다.

나는 다음과 같이 접근하였다.

1. 먼저 다리를 놓아야할 모든 엣지를 구한다. (즉, 주위에 0이 있다면 다리가 건설 가능한것으로 보고 큐에 해당 지점을 전부 푸시한다.)

2. dfs를 통해 구역별로 값을 따로 매긴다. 나는 처음 영역을 2부터 매겼는데 그 이유는 1은 이미 입력으로 들어온 값이기 때문에 혼동을 피하기 위함이다. 

3. 1번에서 받은 모든 엣지를 통해 다리를 건설하기 시작한다. BFS를 사용하는게 현명하다 왜냐면 모든 값을 조사할 필요 없이, 최소 값만 알면 되기 때문이다. 

절차는 처음에 해당 지점이 몇번째 구역인지 값을 통해 area에 담고, bridge라는 큐에 담는다. 그리고 큐를 통해 사방을 검색하며 BFS를 진행하면 된다. 

여기서 주의해야할 점이 있다. 나는 메모리 초과로 상당히 애먹었다...

1. 만약 ans(현재까지 최소값)보다 현재 cnt(현재 건설중인 다리 수)가  크다면 이는 의미가 없으므로 종료시킨다.
   (시간 초과 방지)

2. BFS로 영역을 확장할때 0인 값과 다른구역의 값을 한번에 큐에 집어넣고 큐가 다음 반복될때 현재 위치가 다른 값이면 이라는 이프문으로 확인시킬수도 있다. 그러나 이렇게하면 시간 및 메모리가 낭비되므로 나처럼 분할시키는 것이 도움이 된다. 

3. 하다보면 1로 둘러 쌓인 지역이 있을것이다. 이런 경우는 만약 0을 기준으로 동서남 쪽이 1이면 3번이 푸시가 된다. 이건 피하기보다는 일단 담는다. 하지만, 어느 한쪽에서 사용되면 -1로 값을 변경하였기 때문에, 아래의 모든 과정을 스킵하게 해야한다. 하고 안하고는 메모리 초과이냐 정답이냐를 가른다. 매우 중요한데 너무 오랜만에 BFS를 하여 실수를 하였다.

이 부분만 잡는다면 그리 어렵지는 않은 문제이다. 다만 귀찮은 문제인데, 시험용으로는 정말 좋은 문제같다. 이런건 보통 KOI에서 정말 많이 봤었다..

출처 : https://www.acmicpc.net/problem/9813

내답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/9813.cpp

하.. 이문제 그냥 간단한 재귀일줄 알았다.. 하지만 매우 손이 많이가는 문제였다. 괜히 정답자가 1명인게 아니었다. 

먼저 나는 정답을 맞지 못했다. 그러나 내 답이 맞다고 생각한다. 정답자 소스에서 반례를 찾았기 때문이다.

먼저 문제설명을 하자면 숫자가 5개 입력이 들어오고 첫번재 수가 -1이면 프로그램이 종료이고 그게 아니라면 계속 입력을 받는다.

수는 1번째부터 4번째까지의 수로 어떻게 계산을 하든 5번째 수를 만들도록 하는것이며 최종적으로 불가능하다면 NO! 를 출력하는 것이다. 

이 문제는 내가 정말 많이 해맸다. 문제 해설이 약간 빈약했던것 같다.

우선 기본적인 접근은 다음과 같다.

1. +, -, *, / 이 네가지 산술기호를 재귀로 전부 할당한다 수는 4개뿐이므로 산술기호는 3개로 한정되어 있다. +++부터 ///까지 모두 대입한다. 

2. 괄호를 칠 수 있다. 하지만 문제에서 하나의 연산자만 가능하다고 하였으니 이중괄호는 없다고 가정하고 시작한다. 괄호는 패턴을 나눠보면 다음과 같다.

//case 1 (a, b), c, d

//case 2 a, (b, c), d

//case 3 a, b, (c, d)

//case 4 (a, b), (c, d)

//case 5 (a, b, c), d

//case 6 a, (b, c, d)

//case 7 a, b, c, d

위와 같이 총 7가지 경우가 나온다.  이 경우에 맞춰 전부 대입해보면 된다. 

하지만 유의할점이 있다.

문제 어디에서도 수가 바뀌지 않아도 된다는 말은 없다. 즉 1번째 수부터 4번째 수까지 위치가 바뀌기도 한다. 

예를들어 a, b, c, d 로는 어떠한 방법으로도 e를 만들 수 없더라도 d a c b 이렇게 순서를 바꾸면 될 수도 있다. 실제로 이런 경우는 존재한다.

그러므로 다시 4가지 수를 모든 경우의 수에 따라 재귀를 돌려줘야한다. 

그리고 두번째 유의할 점

나누기는 언제나 짜증나는 것인데, 만약 예외처리를 하지 않는다면 1/0 이렇게 0으로 나누라는 경우가 발생할것이고 프로그램은 죽게 될 것이다. 그렇기 때문에 반드시 예외 처리를 해야한다.

그리고 3/2 이런수는 당연히 1.5이다. 하지만 int로만 처리하면 이 수는 1이 되고 e가 1이라면 같다고 판단할 수 있다. 그러므로 이 부분도 처리를 따로 해줘야 피해갈 수 있다.

그럼에도 불구하고 나는 오답을 맞았다. 그리고 구글링을 통해 정답자의 소스를 구했는데 특이한 반례를 찾았다.
원문 링크

16 15 17 50 9 다음의 수가 들어오면 나는 ok를 주고 정답자는 no를 준다. 

그런데 이경우 수를 50 17 15 16 9 이렇게 정렬하고 식을 50 / (17-15) -16 이렇게 가공하면 9가 나올 수 있다. 그런데 정답자 소스에는 이 경우 NO를 출력하게 하였다. 아마 이 부분의 차이와 같은 문제로 오답을 맞은 것 같다. 

그런데 신기한건 30 4 2 5 10 이수를 주고 동일한 패턴을 대입하면 정답자소스도 OK를 주게 된다. 뭔가 이건 이상하다.

그래서 나는 내 소스가 맞고 정답테스트케이스 및 정답소스가 틀렸다고 생각했다. 뭐 케이스를 다 열어보고 대조를 해봐야 알겠지만, 확실히 이상한 부분이고 내가 맞다고 생각한다. 

그래서 셀프 정답처리를 하고 넘어가야겠다. 

P.S.

소스를 최대한 간소하게 하려고 함수를 이것저것 써넣으며 반복시켰는데, 그래도 길다...