자바 | 백준 | 1034 | 램프

solution 1. 재귀 이용한 완전 탐색 → 시간초과

import java.io.*;
import java.util.*;

public class Main {

	static int N, M, K;
	static int max = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int[][] map = new int[N][M];
		for (int i = 0; i < N; i++) {
			String S = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = S.charAt(j) - '0';
			}
		}
		K = Integer.parseInt(br.readLine());
		// 입력 끝
		dfs(map, 0);
		System.out.println(max);
	}

	static void dfs(int[][] map, int k) {
		if (k == K) {
			max = Math.max(max, getOnRow(map));
			return;
		}
		
		for (int i = 0; i < map[0].length; i++) {
			dfs(onOff(map, i), k+1);
			map = onOff(map, i);
		}
	}

	static int getOnRow(int[][] map) {
		int onCnt = 0;
		for (int i = 0; i < map.length; i++) {
			int j = 0;
			for (j = 0; j < map[0].length; j++) {
				if (map[i][j] == 0)
					break;
			}
			if (j == map[0].length) {
				onCnt++;
			}
		}
		return onCnt;
	}


	static int[][] onOff(int[][] map, int col) {
		for (int i = 0; i < map.length; i++) {
			if (map[i][col] == 0)
				map[i][col] = 1;
			else
				map[i][col] = 0;
		}
		return map;
	}
	
}

---

solution 2.

1) 처음부터 다르게 생긴 행은 스위치를 몇 번을 눌러도(켰을 때, 껐을 때 두 가지 경우밖에 없으니까) 절대 같이 켜질 수 없다.

2) 행 별로 꺼져 있는 램프가 몇 갠지 구한다.

3) 꺼져있는 램프 수가 K보다 작거나 같다면, 홀수개인지 짝수개인지 확인한다.

4) ex. K는 짝수인데 꺼져있는 램프 수는 홀수개라면 행 내의 모든 램프를 켤 수 없다.

5) K보다 작거나 같고, 홀짝 같다면 자신과 같은 행이 몇 개인지 찾는다. (visited도 같이 체크한다.)

package BOJ;

import java.io.*;
import java.util.*;

public class BOJ_1034_램프 {

	static int N, M, K;
	static int max = Integer.MIN_VALUE;
	static int[][] map;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			String S = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = S.charAt(j) - '0';
			}
		}
		K = Integer.parseInt(br.readLine());
		// 입력 끝
		visited = new boolean[N];

		// 다르게 생긴 행은 같이 켜질 수 없다.
		for (int i = 0; i < N; i++) {
			if (visited[i])
				continue;
			visited[i] = true;

			int offLamp = 0;
			for (int lamp : map[i]) {
				if (lamp == 0) {
					offLamp++;
				}
			}

			int sameRowCnt = getSameRowCnt(i); // 같은 행 몇 갠지 세고, visited 체크
//			System.out.println(i+" "+offLamp + " "+sameRowCnt);
			if (offLamp % 2 == K % 2 && offLamp <= K) {
				max = Math.max(sameRowCnt, max);
			}
		}
		System.out.println(max);
	}

	static int getSameRowCnt(int r) {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			// 배열 두 개의 내용물이 같은지 비교:  Arrays.equals(arr1, arr2)
			if (Arrays.equals(map[i], map[r])) {
				cnt++;
				visited[i] = true;
			}
		}
		return cnt;
	}

}

max를 Integer.MAX_VALUE로 초기화하는 게 습관이 됐는데 개수를 구하는거니까 최소값은 0이다.

 

www.acmicpc.net/problem/1034

1034번: 램프