Code up 4060 전광판 전구 조작

  Ex)

java

열기 줄바꿈

/*

5 6
0 0 1 0 1 1
0 1 1 0 0 0
0 0 1 0 0 0
1 1 1 1 1 1
0 0 0 1 0 0

 */

import java.util.Scanner;
public class Billboard {
	
	static int M, N;
	static int MAX_COUNT = 501;
	static int[][] AdjMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int[][] VisitMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int[][] DirMatrix = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int DIRECTION = 4;
	static int cnt = 0;
	static int[] AreaArray = new int[MAX_COUNT];
	static int[] AreaArrayOff = new int[MAX_COUNT];
	
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		M = scan.nextInt();
		N = scan.nextInt();
		
		for(int i = 1; i <= M; ++i){
			for(int j = 1; j <= N; ++j){
				AdjMatrix[i][j] = scan.nextInt();
			}
		}
		
		for(int i = 1; i <= M; ++i){
			for(int j = 1; j <= N; ++j){
				if(0 == VisitMatrix[i][j] && 0 == AdjMatrix[i][j]) {
					++cnt;
					++AreaArray[cnt];
					OnMethod(i, j);
				}
			}
		}
		System.out.println(cnt + " ");
		
			for(int i = 1; i <= M; ++i) {
				for(int j =1; j <= N;++j) {
					VisitMatrix[i][j] = 0;
				}
			}
			
		cnt = 0;
			
		for(int i = 1; i <= M; ++i){
			for(int j = 1; j <= N; ++j){
				if(0 == VisitMatrix[i][j] && 1 == AdjMatrix[i][j]) {
					++cnt;
					++AreaArrayOff[cnt];
					OffMethod(i, j);
				}
			}
		}
		System.out.println(cnt);
	}
	
	public static void OnMethod(int _CurrRow, int _CurrCol) {
		
		VisitMatrix[_CurrRow][_CurrCol] = 1;
		for(int i = 0; i < DIRECTION; ++i) {
			
			int nextRow = _CurrRow + DirMatrix[i][0];
			int nextCol = _CurrCol + DirMatrix[i][1];
			if(1 == VisitMatrix[nextRow][nextCol]) continue;
			if(0 == AdjMatrix[nextRow][nextCol] &&
			   1 <= nextRow && nextRow <= M &&
			   1 <= nextCol && nextCol <= N	) {
					++AreaArray[cnt];
					System.out.printf("ArrayCnt[%d]: %d  , (%d, %d) -> (%d, %d)\n",cnt, AreaArray[cnt], _CurrRow, _CurrCol, nextRow, nextCol );
					OnMethod(nextRow, nextCol);
			}
		}
	}
	
	public static void OffMethod(int _CurrRow, int _CurrCol) {
		
		VisitMatrix[_CurrRow][_CurrCol] = 1;
		for(int i = 0; i < DIRECTION; ++i) {
			int nextRow = _CurrRow + DirMatrix[i][0];
			int nextCol = _CurrCol + DirMatrix[i][1];
			if(1 == VisitMatrix[nextRow][nextCol]) continue;
			if(1 == AdjMatrix[nextRow][nextCol] &&
			   1 <= nextRow && nextRow <= M &&
			   1 <= nextCol && nextCol <= N	) {
					++AreaArrayOff[cnt];
					System.out.printf("ArrayCntOff[%d]: %d  , (%d, %d) -> (%d, %d)\n", cnt, AreaArrayOff[cnt], _CurrRow, _CurrCol, nextRow, nextCol );
					OffMethod(nextRow, nextCol);
			}
		}
	}
}

 

  Note) 실행 결과

java

열기 줄바꿈

입력
5 6
0 0 1 0 1 1
0 1 1 0 0 0
0 0 1 0 0 0
1 1 1 1 1 1
0 0 0 1 0 0

출력
ArrayCnt[1]: 2  , (1, 1) -> (2, 1)
ArrayCnt[1]: 3  , (2, 1) -> (3, 1)
ArrayCnt[1]: 4  , (3, 1) -> (3, 2)
ArrayCnt[1]: 5  , (1, 1) -> (1, 2)
ArrayCnt[2]: 2  , (1, 4) -> (2, 4)
ArrayCnt[2]: 3  , (2, 4) -> (3, 4)
ArrayCnt[2]: 4  , (3, 4) -> (3, 5)
ArrayCnt[2]: 5  , (3, 5) -> (2, 5)
ArrayCnt[2]: 6  , (2, 5) -> (2, 6)
ArrayCnt[2]: 7  , (2, 6) -> (3, 6)
ArrayCnt[3]: 2  , (5, 1) -> (5, 2)
ArrayCnt[3]: 3  , (5, 2) -> (5, 3)
ArrayCnt[4]: 2  , (5, 5) -> (5, 6)
4 
ArrayCntOff[1]: 2  , (1, 3) -> (2, 3)
ArrayCntOff[1]: 3  , (2, 3) -> (3, 3)
ArrayCntOff[1]: 4  , (3, 3) -> (4, 3)
ArrayCntOff[1]: 5  , (4, 3) -> (4, 2)
ArrayCntOff[1]: 6  , (4, 2) -> (4, 1)
ArrayCntOff[1]: 7  , (4, 3) -> (4, 4)
ArrayCntOff[1]: 8  , (4, 4) -> (5, 4)
ArrayCntOff[1]: 9  , (4, 4) -> (4, 5)
ArrayCntOff[1]: 10  , (4, 5) -> (4, 6)
ArrayCntOff[1]: 11  , (2, 3) -> (2, 2)
ArrayCntOff[2]: 2  , (1, 5) -> (1, 6)
2

  - DFS 메서드를 두 개 만든다.

  - 전구를 켜지도록 할 때는 On 메서드, 끄기 위해서는 Off메서드를 사용한다.

    -> AdjMatrix의 값만 1 또는 0으로 바뀌고 나머지는 메서드 식이 같다. 

  -  DFS 메서드를 실행하기 전 메인 함수에서 ++cnt, ++ArrayCnt를 해주고 DFS메서드 안에서 

    -> 재귀함수가 실행되기 전에 또 다시 ++ArrayCnt를 해주면 배열별로 값을 저장할 수 있다.