FilesExpand file tree

master

/

6.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

180 lines (162 loc) · 5.86 KB

master

/

6.java

Copy path

Top

File metadata and controls

• Code
• Blame

180 lines (162 loc) · 5.86 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

import java.util.*;

class Combination {

private int n;

private int r;

private int[] now; // 현재 조합

private ArrayList<ArrayList<Position>> result; // 모든 조합

public ArrayList<ArrayList<Position>> getResult() {

return result;

}

public Combination(int n, int r) {

this.n = n;

this.r = r;

this.now = new int[r];

this.result = new ArrayList<ArrayList<Position>>();

}

public void combination(ArrayList<Position> arr, int depth, int index, int target) {

if (depth == r) {

ArrayList<Position> temp = new ArrayList<>();

for (int i = 0; i < now.length; i++) {

temp.add(arr.get(now[i]));

}

result.add(temp);

return;

}

if (target == n) return;

now[index] = target;

combination(arr, depth + 1, index + 1, target + 1);

combination(arr, depth, index, target + 1);

}

}

class Position {

private int x;

private int y;

public Position(int x, int y) {

this.x = x;

this.y = y;

}

public int getX() {

return this.x;

}

public int getY() {

return this.y;

}

}

public class Main {

public static int n; // 복도의 크기

public static char[][] board = new char[6][6]; // 복도 정보 (N x N)

public static ArrayList<Position> teachers = new ArrayList<>(); // 모든 선생님 위치 정보

public static ArrayList<Position> spaces = new ArrayList<>(); // 모든 빈 공간 위치 정보

// 특정 방향으로 감시를 진행 (학생 발견: true, 학생 미발견: false)

public static boolean watch(int x, int y, int direction) {

// 왼쪽 방향으로 감시

if (direction == 0) {

while (y >= 0) {

if (board[x][y] == 'S') { // 학생이 있는 경우

return true;

}

if (board[x][y] == 'O') { // 장애물이 있는 경우

return false;

}

y -= 1;

}

}

// 오른쪽 방향으로 감시

if (direction == 1) {

while (y < n) {

if (board[x][y] == 'S') { // 학생이 있는 경우

return true;

}

if (board[x][y] == 'O') { // 장애물이 있는 경우

return false;

}

y += 1;

}

}

// 위쪽 방향으로 감시

if (direction == 2) {

while (x >= 0) {

if (board[x][y] == 'S') { // 학생이 있는 경우

return true;

}

if (board[x][y] == 'O') { // 장애물이 있는 경우

return false;

}

x -= 1;

}

}

// 아래쪽 방향으로 감시

if (direction == 3) {

while (x < n) {

if (board[x][y] == 'S') { // 학생이 있는 경우

return true;

}

if (board[x][y] == 'O') { // 장애물이 있는 경우

return false;

}

x += 1;

}

}

return false;

}

// 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사

public static boolean process() {

// 모든 선생의 위치를 하나씩 확인

for (int i = 0; i < teachers.size(); i++) {

int x = teachers.get(i).getX();

int y = teachers.get(i).getY();

// 4가지 방향으로 학생을 감지할 수 있는지 확인

for (int j = 0; j < 4; j++) {

if (watch(x, y, j)) {

return true;

}

}

}

return false;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

board[i][j] = sc.next().charAt(0);

// 선생님이 존재하는 위치 저장

if (board[i][j] == 'T') {

teachers.add(new Position(i, j));

}

// 장애물을 설치할 수 있는 (빈 공간) 위치 저장

if (board[i][j] == 'X') {

spaces.add(new Position(i, j));

}

}

}

// 빈 공간에서 3개를 뽑는 모든 조합을 확인

Combination comb = new Combination(spaces.size(), 3);

comb.combination(spaces, 0, 0, 0);

ArrayList<ArrayList<Position>> spaceList = comb.getResult();

// 학생이 한 명도 감지되지 않도록 설치할 수 있는지의 여부

boolean found = false;

for (int i = 0; i < spaceList.size(); i++) {

// 장애물들을 설치해보기

for (int j = 0; j < spaceList.get(i).size(); j++) {

int x = spaceList.get(i).get(j).getX();

int y = spaceList.get(i).get(j).getY();

board[x][y] = 'O';

}

// 학생이 한 명도 감지되지 않는 경우

if (!process()) {

// 원하는 경우를 발견한 것임

found = true;

break;

}

// 설치된 장애물을 다시 없애기

for (int j = 0; j < spaceList.get(i).size(); j++) {

int x = spaceList.get(i).get(j).getX();

int y = spaceList.get(i).get(j).getY();

board[x][y] = 'X';

}

}

if (found) System.out.println("YES");

else System.out.println("NO");

}

}