|
| 1 | +importjava.util.*; |
| 2 | + |
| 3 | +classCombination { |
| 4 | +privateintn; |
| 5 | +privateintr; |
| 6 | +privateint[]now;// 현재 조합 |
| 7 | +privateArrayList<ArrayList<Position>>result;// 모든 조합 |
| 8 | + |
| 9 | +publicArrayList<ArrayList<Position>>getResult() { |
| 10 | +returnresult; |
| 11 | + } |
| 12 | + |
| 13 | +publicCombination(intn,intr) { |
| 14 | +this.n =n; |
| 15 | +this.r =r; |
| 16 | +this.now =newint[r]; |
| 17 | +this.result =newArrayList<ArrayList<Position>>(); |
| 18 | + } |
| 19 | + |
| 20 | +publicvoidcombination(ArrayList<Position>arr,intdepth,intindex,inttarget) { |
| 21 | +if (depth ==r) { |
| 22 | +ArrayList<Position>temp =newArrayList<>(); |
| 23 | +for (inti =0;i <now.length;i++) { |
| 24 | +temp.add(arr.get(now[i])); |
| 25 | + } |
| 26 | +result.add(temp); |
| 27 | +return; |
| 28 | + } |
| 29 | +if (target ==n)return; |
| 30 | +now[index] =target; |
| 31 | +combination(arr,depth +1,index +1,target +1); |
| 32 | +combination(arr,depth,index,target +1); |
| 33 | + } |
| 34 | +} |
| 35 | + |
| 36 | +classPosition { |
| 37 | +privateintx; |
| 38 | +privateinty; |
| 39 | + |
| 40 | +publicPosition(intx,inty) { |
| 41 | +this.x =x; |
| 42 | +this.y =y; |
| 43 | + } |
| 44 | + |
| 45 | +publicintgetX() { |
| 46 | +returnthis.x; |
| 47 | + } |
| 48 | + |
| 49 | +publicintgetY() { |
| 50 | +returnthis.y; |
| 51 | + } |
| 52 | +} |
| 53 | + |
| 54 | +publicclassMain { |
| 55 | + |
| 56 | +publicstaticintn;// 복도의 크기 |
| 57 | +publicstaticchar[][]board =newchar[6][6];// 복도 정보 (N x N) |
| 58 | +publicstaticArrayList<Position>teachers =newArrayList<>();// 모든 선생님 위치 정보 |
| 59 | +publicstaticArrayList<Position>spaces =newArrayList<>();// 모든 빈 공간 위치 정보 |
| 60 | + |
| 61 | +// 특정 방향으로 감시를 진행 (학생 발견: true, 학생 미발견: false) |
| 62 | +publicstaticbooleanwatch(intx,inty,intdirection) { |
| 63 | +// 왼쪽 방향으로 감시 |
| 64 | +if (direction ==0) { |
| 65 | +while (y >=0) { |
| 66 | +if (board[x][y] =='S') {// 학생이 있는 경우 |
| 67 | +returntrue; |
| 68 | + } |
| 69 | +if (board[x][y] =='O') {// 장애물이 있는 경우 |
| 70 | +returnfalse; |
| 71 | + } |
| 72 | +y -=1; |
| 73 | + } |
| 74 | + } |
| 75 | +// 오른쪽 방향으로 감시 |
| 76 | +if (direction ==1) { |
| 77 | +while (y <n) { |
| 78 | +if (board[x][y] =='S') {// 학생이 있는 경우 |
| 79 | +returntrue; |
| 80 | + } |
| 81 | +if (board[x][y] =='O') {// 장애물이 있는 경우 |
| 82 | +returnfalse; |
| 83 | + } |
| 84 | +y +=1; |
| 85 | + } |
| 86 | + } |
| 87 | +// 위쪽 방향으로 감시 |
| 88 | +if (direction ==2) { |
| 89 | +while (x >=0) { |
| 90 | +if (board[x][y] =='S') {// 학생이 있는 경우 |
| 91 | +returntrue; |
| 92 | + } |
| 93 | +if (board[x][y] =='O') {// 장애물이 있는 경우 |
| 94 | +returnfalse; |
| 95 | + } |
| 96 | +x -=1; |
| 97 | + } |
| 98 | + } |
| 99 | +// 아래쪽 방향으로 감시 |
| 100 | +if (direction ==3) { |
| 101 | +while (x <n) { |
| 102 | +if (board[x][y] =='S') {// 학생이 있는 경우 |
| 103 | +returntrue; |
| 104 | + } |
| 105 | +if (board[x][y] =='O') {// 장애물이 있는 경우 |
| 106 | +returnfalse; |
| 107 | + } |
| 108 | +x +=1; |
| 109 | + } |
| 110 | + } |
| 111 | +returnfalse; |
| 112 | + } |
| 113 | + |
| 114 | +// 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사 |
| 115 | +publicstaticbooleanprocess() { |
| 116 | +// 모든 선생의 위치를 하나씩 확인 |
| 117 | +for (inti =0;i <teachers.size();i++) { |
| 118 | +intx =teachers.get(i).getX(); |
| 119 | +inty =teachers.get(i).getY(); |
| 120 | +// 4가지 방향으로 학생을 감지할 수 있는지 확인 |
| 121 | +for (intj =0;j <4;j++) { |
| 122 | +if (watch(x,y,j)) { |
| 123 | +returntrue; |
| 124 | + } |
| 125 | + } |
| 126 | + } |
| 127 | +returnfalse; |
| 128 | + } |
| 129 | + |
| 130 | +publicstaticvoidmain(String[]args) { |
| 131 | +Scannersc =newScanner(System.in); |
| 132 | + |
| 133 | +n =sc.nextInt(); |
| 134 | + |
| 135 | +for (inti =0;i <n;i++) { |
| 136 | +for (intj =0;j <n;j++) { |
| 137 | +board[i][j] =sc.next().charAt(0); |
| 138 | +// 선생님이 존재하는 위치 저장 |
| 139 | +if (board[i][j] =='T') { |
| 140 | +teachers.add(newPosition(i,j)); |
| 141 | + } |
| 142 | +// 장애물을 설치할 수 있는 (빈 공간) 위치 저장 |
| 143 | +if (board[i][j] =='X') { |
| 144 | +spaces.add(newPosition(i,j)); |
| 145 | + } |
| 146 | + } |
| 147 | + } |
| 148 | + |
| 149 | +// 빈 공간에서 3개를 뽑는 모든 조합을 확인 |
| 150 | +Combinationcomb =newCombination(spaces.size(),3); |
| 151 | +comb.combination(spaces,0,0,0); |
| 152 | +ArrayList<ArrayList<Position>>spaceList =comb.getResult(); |
| 153 | + |
| 154 | +// 학생이 한 명도 감지되지 않도록 설치할 수 있는지의 여부 |
| 155 | +booleanfound =false; |
| 156 | +for (inti =0;i <spaceList.size();i++) { |
| 157 | +// 장애물들을 설치해보기 |
| 158 | +for (intj =0;j <spaceList.get(i).size();j++) { |
| 159 | +intx =spaceList.get(i).get(j).getX(); |
| 160 | +inty =spaceList.get(i).get(j).getY(); |
| 161 | +board[x][y] ='O'; |
| 162 | + } |
| 163 | +// 학생이 한 명도 감지되지 않는 경우 |
| 164 | +if (!process()) { |
| 165 | +// 원하는 경우를 발견한 것임 |
| 166 | +found =true; |
| 167 | +break; |
| 168 | + } |
| 169 | +// 설치된 장애물을 다시 없애기 |
| 170 | +for (intj =0;j <spaceList.get(i).size();j++) { |
| 171 | +intx =spaceList.get(i).get(j).getX(); |
| 172 | +inty =spaceList.get(i).get(j).getY(); |
| 173 | +board[x][y] ='X'; |
| 174 | + } |
| 175 | + } |
| 176 | + |
| 177 | +if (found)System.out.println("YES"); |
| 178 | +elseSystem.out.println("NO"); |
| 179 | + } |
| 180 | +} |