알고리즘 문제해결전략 2.3 순서를 강제할 수 있을까? 풀이좀 가능할까요 ㅠ ㅠ

Question

책 37, 38p 문제인데 해당 문제의 풀이법을 알고싶습니다.문제는 5x5 격자의 모든칸의 불을 켜는 문제입니다.한칸을 클릭하면 그 칸과 상하좌우 칸들의 상태가 변합니다.켜져있으면 꺼지고 꺼져있으면 켜지게요.. 책에서보니 2^5 시간복잡도로 해결이가능한것같은데 어떻게해야할지 갈피가 잡히지 않습니다.순서를 강제해서 풀어봐도 꼭 1개가 남습니다.아래코드는 제가 작성해본 코드입니다.첫째 줄 하나씩 클릭해도 풀어지지 않고, 첫째 줄을 클릭하지 않아도 풀어지지 않습니다0= 불 꺼짐 1= 불 켜짐제 풀이코드 public static void main(String[] args) throws InterruptedException { int [][]ints = { { 0, 1, 1, 0, 1 }, { 1, 1, 1, 0, 0 }, { 0, 1, 0, 1, 1 }, { 0, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0 } }; for (int j = 0; j < 5; j++) { int [][]copys = new int[5][5]; for (int i = 0; i < 5; i++) { copys[i] = ints[i].clone(); } //첫째 줄 하나씩 클릭 onClick(copys, 0, j); for (int row = 1; row < copys.length; row++) { for (int i1 = 0; i1 < copys[row].length; i1++) { if(copys[row-1][i1] == 0) { onClick(copys, row, i1); } } } //결과 출력 for (int[] anInt : copys) { for (int i : anInt) { System.out.printf("%4s", i == 0 ? "□":"■"); } System.out.println(); } System.out.println(); } //초기값 출력 System.out.println(); for (int[] anInt : ints) { for (int i : anInt) { System.out.printf("%4s", i == 0 ? "□":"■"); } System.out.println(); } } public static void onClick(int[][] a, int yIdx, int xIdx){ a[yIdx][xIdx] ^= 1; if(yIdx > 0){ a[yIdx-1][xIdx] ^= 1; } if(yIdx < 4){ a[yIdx+1][xIdx] ^= 1; } if(xIdx > 0){ a[yIdx][xIdx-1] ^= 1; } if(xIdx < 4){ a[yIdx][xIdx+1] ^= 1; } }

비정규분포 · Answer

올림피아드 수준 문제인데, 책 내용도 안 알려주면 지나가던 사람들이 어떻게 문제를 풀어 드릴까요...

알고리즘 문제해결전략 2.3 순서를 강제할 수 있을까? 풀이좀 가능할까요 ㅠ ㅠ

1개의 답변

기술 목록