c언어 26124번 조명 배치 (백준)

#include <stdio.h>

int main(void)
{
	int n, w; //input
	scanf("%d %d", &n, &w);
	int map[n+2][w+2];
	for(int i = 0; i<w+2; i++) map[0][i] = map[n+1][i] = -1; //외각을 -1로
	for(int i = 1; i<=n; i++) {
		map[i][0] = -1; //외각을 -1로
		for(int j = 1; j<=w; j++) scanf("%d", &map[i][j]);
		map[i][w+1]=-1; //외각을 -1로
	}
	
	int ans = 0;
	int exit = 0;
	
	for(int i = 1; i<n+1; i++) { //가능한지 아닌지, 그리고 전구가 몇 개 인지 판별
		for(int j = 1; j<w+1; j++) {
			if(map[i][j] == -1) continue;
			
			if(map[i-1][j] != -1) 
			if(map[i][j] != map[i-1][j] && map[i][j] != map[i-1][j]+1) {
				if(map[i][j] != map[i-1][j]-1) exit++;
				continue;
			}
			if(map[i+1][j] != -1)
			if(map[i][j] != map[i+1][j] && map[i][j] != map[i+1][j]+1) {
				if(map[i][j] != map[i+1][j]-1) exit++;
				continue;
			} 
			if(map[i][j-1] != -1)
			if(map[i][j] != map[i][j-1] && map[i][j] != map[i][j-1]+1) {
				if(map[i][j] != map[i][j-1]-1) exit++;
				continue;
			}
			if(map[i][j+1] != -1)
			if(map[i][j] != map[i][j+1] && map[i][j] != map[i][j+1]+1) {
				if(map[i][j] != map[i][j+1]-1) exit++;
				continue;	
			}
			if(map[i][j] > 0) ans++;
		}
	} 
	
	if(exit) ans = -1;
	printf("%d", ans);
	
}

 

https://www.acmicpc.net/problem/26124

26124번: 조명 배치

 

풀이 : 브루트 포스

1. 입력받은 것들의 상하좌우를 -1 (=벽)으로 감싼다.

input 1 2 3  -> -1 -1 -1 -1 -1

         2 3 3      -1  1  2  3  -1

         3 4 5      -1  2  3  3  -1

                       -1  3  4  5  -1

                       -1 -1 -1 -1 -1

 

2. 전구 판별 및 가능성 판별

2-1)  가운데를 기준으로 상하좌우의 값과의 차이가 1 이내로 돼야 함. 차이가 2 이상이면 불가능 (-1 = 벽은 제외한다)

2-2) 전구의 조건은 2-1)을 따르되, 가운데 값이 상하좌우의 값보다 같거나 커야 함

 

3. 불가능이면 -1, 가능하면 전구의 개수를 출력한다.