[CodeForce] Water The Garden .A 알고리즘 스터디

알고리즘 스터디 

두번째 풀어볼 문제는 아래 주소를 적어 두었습니다. 

http://codeforces.com/contest/920/problem/A

A. Water The Garden

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

It is winter now, and Max decided it's about time he watered the garden.

The garden can be represented as n consecutive garden beds, numbered from 1 to n. k beds contain water taps (i-th tap is located in the bed xi), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed xi is turned on, then after one second has passed, the bed xi will be watered; after two seconds have passed, the beds from the segment [xi - 1, xi + 1] will be watered (if they exist); after j seconds have passed (jis an integer number), the beds from the segment [xi - (j - 1), xi + (j - 1)] will be watered (if they exist). Nothing changes during the seconds, so, for example, we can't say that the segment [xi - 2.5, xi + 2.5]will be watered after 2.5 seconds have passed; only the segment [xi - 2, xi + 2] will be watered at that moment.

The garden from test 1. White colour denotes a garden bed without a tap, red colour — a garden bed with a tap.The garden from test 1 after 2 seconds have passed after turning on the tap. White colour denotes an unwatered garden bed, blue colour — a watered bed.

Max wants to turn on all the water taps at the same moment, and now he wonders, what is the minimum number of seconds that have to pass after he turns on some taps until the whole garden is watered. Help him to find the answer!

Input

The first line contains one integer t — the number of test cases to solve (1 ≤ t ≤ 200).

Then t test cases follow. The first line of each test case contains two integers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n) — the number of garden beds and water taps, respectively.

Next line contains k integers xi (1 ≤ xi ≤ n) — the location of i-th water tap. It is guaranteed that for each  condition xi - 1 < xi holds.

It is guaranteed that the sum of n over all test cases doesn't exceed 200.

Note that in hacks you have to set t = 1.

Output

For each test case print one integer — the minimum number of seconds that have to pass after Max turns on some of the water taps, until the whole garden is watered.

Example

input

Copy

3
5 1
3
3 3
1 2 3
4 1
1

output

Copy

3
1
4

Note

The first example consists of 3 tests:

1. There are 5 garden beds, and a water tap in the bed 3. If we turn it on, then after 1 second passes, only bed 3 will be watered; after 2 seconds pass, beds [1, 3] will be watered, and after 3 seconds pass, everything will be watered.
2. There are 3 garden beds, and there is a water tap in each one. If we turn all of them on, then everything will be watered after 1 second passes.
3. There are 4 garden beds, and only one tap in the bed 1. It will take 4 seconds to water, for example, bed 4.

문제의 내용은 위와 같구요. 일단 영어 문제이지만, 

하루 종일 번역하고 생각 해본 결과 BFS 문제 같다고 생각했습니다. 

문제의 내용은 물을 주고 싶은데 1초당 양쪽으로 1칸씩 물을 줄 수 있습니다. 

그리고 Max 님은 물을 키는 tab 을 한번에 다 Turn On 하실 수 있구요.

최단 시간안에 모든 칸에 물을 주는 것이 목적 입니다. ( BFS ) 

Test Case >> 땅의 넒이 >> Tab의 갯수 

탭의 위치 를 입력 받습니다. 

그리고 최단 시간으로 모든 칸에 물을 줄 초를 출력 하는 거죠.

(예제 확인)

5 1
3

---> 3

잘 보시면 5개의 칸 그리고 1개의 Tab 이 주어집니다. 

1 | 2 | 3 | 4 | 5 

          *         <------- 이렇게 3번째 위치에 Tab 이 존재 한다면

          *         <-------  1초

     *    *   *    <-------  2초

*   *    *   *   *   <-------  3초 에서 물을 모든 칸에 주고 마무리 됩니다. 

3 3
1 2 3

---> 1

1 | 2 | 3

*   *    * -----> 1초 끝!

4 1
1

---> 4

1 | 2 | 3 | 4

*

*   *

*   *   *

*   *   *    * -----> 4초 끝!

문제 해석은 끝났고, 코딩을 해봅시다. 

------------> 오답 

#include <cstdio>
#include <deque>
#include <memory.h>
#include <iostream>
using namespace std;
deque <int> que;
int t,n,k,curTime, curWater;
int ar[201] = {0,};
int main(){
    scanf("%d", &t);
    for(int tc = 1; tc<=t; tc++){
        curTime = 1;
        memset(ar,0,sizeof(ar));
        que.clear();
        scanf("%d %d", &n, &k);
        curWater = 0;
        for(int i=0; i<k; i++){
            int tab;
            scanf("%d", &tab);
            if(ar[tab] == 1) continue;
            curWater++;
            ar[tab] = 1;
            que.push_back(tab);
        }
        if(curWater == n){
            printf("%d\n", curTime);
            continue;
        }
        int queSize;
        while(curWater != n){
            curTime++;
            queSize = (int)que.size();
            for(int i=0; i<queSize; i++){
                int curIdx = que.front();
                que.pop_front();
                int flag = 0;
                int nextRIdx, nextLIdx;
                nextRIdx = curIdx + curTime - 1;
                nextLIdx = curIdx - curTime + 1;
                if(nextRIdx > 0 && nextRIdx <= n){
                    if(ar[nextRIdx] == 1) continue; /** 1. continue 가 for 문의 처음으로 돌려 놓아서 **/
                    ar[nextRIdx] = 1;
                    curWater++;
                    if(curWater == n) break;
                    flag = 1;
                }
                if(nextLIdx > 0 && nextLIdx <= n){
                    if(ar[nextLIdx] == 1) continue; /** 2. 왼쪽 오른쪽을 다 확인하지 않고 무한반복 **/
                    ar[nextLIdx] = 1;
                    curWater++;
                    if(curWater == n) break;
                    flag = 1;
                }
                if(curWater == n) break;
                if(flag == 1)
                    que.push_back(curIdx);
            }
        }
        printf("%d\n", curTime);
    }
}

정답 --------------->

#include <cstdio>
#include <deque>
#include <memory.h>
#include <iostream>
using namespace std;
deque <int> que;
int t,n,k,curTime, curWater;
int ar[201] = {0,};
int main(){
    scanf("%d", &t);
    for(int tc = 1; tc<=t; tc++){
        curTime = 1;
        memset(ar,0,sizeof(ar));
        que.clear();                //초기화
        scanf("%d %d", &n, &k);
        curWater = 0;
        for(int i=0; i<k; i++){
            int tab;
            scanf("%d", &tab);
            curWater++;             //1초 부터 카운터
            ar[tab] = 1;
            que.push_back(tab);
        }
        if(curWater == n){          //1초에 tab에서 물이 나온다면 답을 출력하고 끝
            printf("%d\n", curTime);
            continue;
        }
        int queSize;
        while(curWater != n){       //빈 bed의 갯수와 물을 채운 갯수를 확인하면서 반복
            curTime++;
            queSize = (int)que.size();  // tab의 갯수를 항상 확인
            for(int i=0; i<queSize; i++){
                int curIdx = que.front();
                que.pop_front();
                int flag = 0;
                int nextRIdx, nextLIdx;
                nextRIdx = curIdx + curTime - 1;    // 왼쪽 오른쪽 방향 시간과 계산
                nextLIdx = curIdx - curTime + 1;
                if(nextRIdx > 0 && nextRIdx <= n && ar[nextRIdx] == 0){
                    ar[nextRIdx] = 1;               // 오른쪽에 물이 차있으면 진행하지 않음
                    curWater++;
                    if(curWater == n) break;
                    flag = 1;
                }
                if(nextLIdx > 0 && nextLIdx <= n && ar[nextLIdx] == 0){
                    ar[nextLIdx] = 1;               // 왼쪽에 물이 차있으면 진행하지 않음
                    curWater++;
                    if(curWater == n) break;
                    flag = 1;
                }
                if(flag == 1)
                    que.push_back(curIdx);          // 왼쪽 혹은 오른쪽에 물을 뿌렸다면 큐에 삽입
            }
        }
        printf("%d\n", curTime);
    }
}
 

Accept 이지만, 무언가 코드가 더럽다... 왼쪽 오른쪽 확인 안하고 그냥 쭉쭉 늘려서 체크해도 될 것 같은데..