백준 18428 - 감시 피하기(Java)

www.acmicpc.net/problem/18428

18428번: 감시 피하기

1. 유형

시뮬레이션

 

2. 자료구조

어레이리스트

 

3. 기능

- 2차원 배열에서 3개 선택 (조합)

- 한 방향으로 끝까지 탐색하기

 

4. 풀이

N*N의 맵에서 3개를 선택하는 경우의 수는 8000 아래다. 즉 브루트포스로 푸는 것이 가능.

 

2차원 배열에서 조합을 구하는 방법은 순서대로 0~N*N-1까지의 수를 한칸마다 할당.

이때 row는 k/N, col는 k%N 공식이 나온다.

k가 2, N이 5라고 치면 (0,2)가 나오는 것이다.

k가 10이라고 치면 (2, 0)이 나온다.

이렇게, 처음 보면 2차월 배열을 1차원으로 만드는 발상이 어려울 수 있다.

 

한 방향으로 끝까지 탐색은 4방향 배열을 만들고 그냥 구현해주면 된다. 이때, 맵을 이탈하거나 장애물을 만나면

반복문을 멈추는 방식이로 구현.

 

코드.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N, cnt;
	static char map[][];
	static ArrayList<Integer> teacher;
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };
	static boolean flag;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		teacher = new ArrayList<>();
		cnt = 0;
		map = new char[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = st.nextToken().charAt(0);
				if (map[i][j] == 'T') {
					teacher.add(cnt);
				}
				cnt++;
			}
		}
		flag = false;
		dfs(0, 0);
		if(flag)
			System.out.println("YES");
		else
			System.out.println("NO");
	}

	static void dfs(int idx, int pick) {
		if (flag)
			return;
		if (idx == N * N) {
			return;
		}
		if (pick == 3) {
			if (find_stu()) {
				flag = true;
			}
			return;
		}
		int r = idx / N;
		int c = idx % N;
		if (map[r][c] == 'X') {
			map[r][c] = 'O';
			dfs(idx + 1, pick + 1);
			map[r][c] = 'X';
		}
		dfs(idx + 1, pick);
	}

	static boolean find_stu() {
		for (int k : teacher) {
			for (int i = 0; i < 4; i++) {
				int cr = k / N;
				int cc = k % N;
				while (true) {
					int nr = cr + dr[i];
					int nc = cc + dc[i];
					if (nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == 'O')
						break;
					if (map[nr][nc] == 'S') {
						return false;
					}
					cr = nr;
					cc = nc;
				}
			}
		}
		return true;
	}
}

5. 느낀점

조합에 대해서 복습할 수 있었음