Daily Algorithm - 와드 설치

문제

Roit games라는 회사에서 만든 대작. 리그오브레전드

2년 전부터 사람 인생을 꼬박꼬박 망치고 있다는 악마의 게임이다. 이 게임에서 가장 중요한 요소는 바로 시야

그 시야를 장악하기 위해서는 '와드' 아이템이 있다. 그 아이템을 사고 원하는 위치에 설치하면 그 반경을 일정 시간동안 밝혀 준다고 한다.

철수는 리그오브레전드의 브론즈 이다. 철수의 친구 영희는 챌린저 이며 매일 매일 브론즈에서 나오고 싶다는 철수의 말에 와드를 연구해 보라 라는 말을 들었고 그 와드를 연구하기 위하여 프로그램을 작성 하기로 했다. 그 프로그램은 이렇다.

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

이렇게 된 9 * 9판에서 한곳에 와드를 설치해보자

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 1 2 2 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 2 2 2 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
와드를 1이라 가정하고
저렇게 와드를 설치하면 
2의 위치와 1의 위치 전부 시야를 밝힌다고 한다.
단 와드의 변수는 부쉬이다

시야 한에 부쉬를 설치해보자

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 1 2 2 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 3 3 3 3 3
0 0 0 0 3 3 3 3 3
0 0 0 0 3 3 3 3 3
부쉬를 3이라 가정하자
부쉬밖에 와드를 설치하면 2의 시야는 밝힐수 있지만 3의 위치인 부쉬는 밝힐수 없다

단,

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 4 3 3 3 3
0 0 2 2 3 3 3 3 3
0 0 2 2 3 3 3 3 3
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
문제에 대한 이해를 위하여 부쉬 + 와드의 위치는 4로 표현한다
이렇게 부쉬 안에 와드를 설치하면
그 와드가 밝힐수 있는 범위 + 지금 내가 속해있는 부쉬 전부를 밝혀준다.

하지만 롤은 또 체계적으로 구성된 게임이기에 와드를 무력화 시켜주는 렌즈가 있다.
렌즈는 와드에 비해 비교적 간단하다

0 0 0 0 0 b b b b
0 0 0 0 0 b b a b
0 0 2 2 2 c c b b
0 0 2 2 2 c c b b
0 0 2 2 1 2 2 0 0
0 0 2 2 2 2 2 0 0
0 0 2 2 2 2 2 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

렌즈의 위치를 a라고 하고 렌즈의 영향범위는 b 와드가 밝혀줄수 있는 시야 + 렌즈의 영향범위는 c라 하면, c의 범위는 와드가 밝혀 줄수 있는 범위에서 제외된다고 한다.

즉 렌즈의 영향범위 안에 와드가 밝혀줄수 있는 범위가 포함되어 있으면 그 범위는 와드가 밝혀 줄수 있는 범위에서 제외되는 것이다.

또 하나의 경우인 렌즈의 영향범위에 와드가 포함되있을 경우이다 만약에 그런 경우에는 와드는 즉시 삭제되어 와드의 기능을 잃어 버린다고 한다.

철수를 위하여 와드가 밝혀 줄 수 있는 넓이를 계산하여라.

입력

첫쨋줄에 와드의 위치인 a1 a2를

둘쨋줄에 렌즈의 위치인 b1 b2가 입력된다

셋쨋줄과 넷쨋줄에는 부쉬의 가장 왼쪽위인 c1,  c2와 가장 오른쪽 아래의 위치인 d1, d2가 입력된다.(부쉬는 직사각형이다.)

(1 <= a1, a2, b1, b2, c1, c2, d1, d2 <= 9 )

출력

와드가 밝혀줄 수 있는 칸의 수를 출력하여라.

예제 입력

5
2 52 23 55 100
4
5 2 55 99

예제 출력

27

풀이

#include <stdio.h>

int main()

{

int map[9][9] = {0,};

int a1, a2, b1, b2, c1, c2, d1, d2;

int wardInBush = 0;

int wardInLens = 0;

int cnt = 0;

scanf("%d %d %d %d %d %d %d %d", &a1, &a2, &b1, &b2, &c1, &c2, &d1, &d2);

map[a1 -1][a2 - 1] = 1;

// 부쉬 부분 처리

for (int i = (c1 -1); i <= (d1 - 1); i++)

{

for (int j = (c2 - 1); j <= (d2 - 1); j++)

{

if (map[i][j] == 1)

{

wardInBush = 1;

continue;

}

map[i][j] = 3;

}

}

// 와드 시야 부분

for (int i = (a1 - 1) - 2; i < (a1 - 1) + 3; i++)

{

for (int j = (a2 - 1) - 2; j < (a2 - 1) + 3; j++)

{

if (map[i][j] != 0 || i < 0 || i >= 9 || j < 0 || j > 8)

continue;

map[i][j] = 2;

}

}

// 와드가 부쉬안에 있을 경우

if (wardInBush == 1)

{

for (int i = (c1 -1); i <= (d1 - 1); i++)

{

for (int j = (c2 - 1); j <= (d2 - 1); j++)

{

if (map[i][j] == 1)

continue;

map[i][j] = 2;

}

}

}

// 렌즈 처리 부분

for (int i = (b1 - 1) - 2; i < (b1 - 1) + 2; i++)

{

for (int j = (b2 - 1) - 2; j < (b2 - 1) + 2; j++)

{

if (i < 0 || i > 8 || j < 0 || j > 8)

continue;

//printf("map[%d][%d] = %d ", i, j, map[i][j]);

if (map[i][j] == 1)

wardInLens = 1;

map[i][j] = 0;

}

//printf("\n");

}

// 와드가 렌즈 범위에 포함될 경우

if (wardInLens == 1)

{

if (wardInBush == 1)

{

for (int i = (c1 -1); i <= (d1 - 1); i++)

{

for (int j = (c2 - 1); j <= (d2 - 1); j++)

{

map[i][j] = 0;

}

}

}

else

{

for (int i = (a1 - 1) - 2; i < (a1 - 1) + 3; i++)

{

for (int j = (a2 - 1) - 2; j < (a2 - 1) + 3; j++)

{

map[i][j] = 0;

}

}

}

}

// 맵 출력

for (int i = 0; i < 9; i++)

{

for (int j = 0; j < 9; j++)

{

if (map[i][j] == 2 || map[i][j] == 1)

cnt++;

}

}

printf("%d", cnt);

return 0;

}

예외 처리를 상당히 주의해서 풀어야 하는 문제.

와드, 부쉬, 렌즈 처리 알고리즘을 구성하는데는 시간이 별로 안걸렸지만, 테스트 케이스를 돌려보며 예외처리를 하는데 많은 시간을 소요했다.

나는 알고리즘 문제를 풀면서 예외처리에 공을 들이지 않는 안좋은 습관이 있었는데, 이 문제를 풀면서 여러가지 예외 발생에 대해 생각하고,

습관을 고치는 계기가 되었다.

문제 출처 : http://codeup.kr/JudgeOnline/problem.php?id=1523