백준 2931번: 가스관

문제 설명

• https://www.acmicpc.net/problem/2931
• M에서부터 Z로까지 가스가 흐르도록 설계되어 있었습니다.
  그런데 중간에 하나의 블록이 지워졌습니다.
  지워진 블록이 어떤 모양인지 구하는 문제입니다.
  불필요한 블록은 존재하지 않으며 외부로 나온 블록은 존재하지 않습니다.

접근법

• M또는 Z에서 BFS를 실행해 끊어지는 지점을 찾았습니다.
• 해당 지점에서 어떤 블록이 적절한지 검사했습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		char[][] board = new char[N][M];

		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}

		int[] place = new int[2];
		Here: for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 'M' || board[i][j] == 'Z') {
					place = BFS(new int[] { i, j }, board);
					break Here;
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append((place[0] + 1) + " ");
		sb.append((place[1] + 1) + " ");
		sb.append(validate(place, board));
		System.out.println(sb.toString());

	}

	// 현재 위치에 어떤 블록이 와야 하는지 판단합니다.
	public static String validate(int[] place, char[][] board) {
		int x = place[0];
		int y = place[1];
		List<Character> ups = new ArrayList<Character>();
		ups.add('|');
		ups.add('+');
		ups.add('1');
		ups.add('4');
		List<Character> downs = new ArrayList<Character>();
		downs.add('|');
		downs.add('+');
		downs.add('2');
		downs.add('3');
		List<Character> lefts = new ArrayList<Character>();
		lefts.add('+');
		lefts.add('-');
		lefts.add('1');
		lefts.add('2');
		List<Character> rights = new ArrayList<Character>();
		rights.add('+');
		rights.add('-');
		rights.add('3');
		rights.add('4');

		if (x - 1 >= 0 && y - 1 >= 0 && x + 1 < N && y + 1 < M && lefts.contains(board[x][y - 1])
				&& rights.contains(board[x][y + 1]) && ups.contains(board[x - 1][y])
				&& downs.contains(board[x + 1][y])) {
			return "+";
		} else if (x - 1 >= 0 && x + 1 < N && ups.contains(board[x - 1][y]) && downs.contains(board[x + 1][y])) {
			return "|";
		} else if (y - 1 >= 0 && y + 1 < M && lefts.contains(board[x][y - 1]) && rights.contains(board[x][y + 1])) {
			return "-";
		} else if (x + 1 < N && y + 1 < M && downs.contains(board[x + 1][y]) && rights.contains(board[x][y + 1])) {
			return "1";
		} else if (x - 1 >= 0 && y + 1 < M && ups.contains(board[x - 1][y]) && rights.contains(board[x][y + 1])) {
			return "2";
		} else if (y - 1 >= 0 && x - 1 >= 0 && lefts.contains(board[x][y - 1]) && ups.contains(board[x - 1][y])) {
			return "3";
		} else if (y - 1 >= 0 && x + 1 < N && lefts.contains(board[x][y - 1]) && downs.contains(board[x + 1][y])) {
			return "4";
		}

		return " ";

	}

	// DFS의 다음 진행방향을 계산해주는 메서드 입니다.
	public static List<int[]> moveNext(int x, int y, char[][] board) {
		char c = board[x][y];
		List<int[]> lst = new ArrayList<int[]>();
		if (c == '|') {
			lst.add(new int[] { x + 1, y });
			lst.add(new int[] { x - 1, y });
		} else if (c == '-') {
			lst.add(new int[] { x, y + 1 });
			lst.add(new int[] { x, y - 1 });
		} else if (c == '+') {
			lst.add(new int[] { x + 1, y });
			lst.add(new int[] { x, y - 1 });
			lst.add(new int[] { x - 1, y });
			lst.add(new int[] { x, y + 1 });
		} else if (c == '1') {
			lst.add(new int[] { x + 1, y });
			lst.add(new int[] { x, y + 1 });
		} else if (c == '2') {
			lst.add(new int[] { x - 1, y });
			lst.add(new int[] { x, y + 1 });
		} else if (c == '3') {
			lst.add(new int[] { x, y - 1 });
			lst.add(new int[] { x - 1, y });
		} else if (c == '4') {
			lst.add(new int[] { x + 1, y });
			lst.add(new int[] { x, y - 1 });
		} else if (c == 'M' || c == 'Z') {
			if (x + 1 < N && board[x + 1][y] != '.') {
				lst.add(new int[] { x + 1, y });
			}
			if (y - 1 >= 0 && board[x][y - 1] != '.') {
				lst.add(new int[] { x, y - 1 });
			}

			if (x - 1 >= 0 && board[x - 1][y] != '.') {
				lst.add(new int[] { x - 1, y });
			}

			if (y + 1 < M && board[x][y + 1] != '.') {
				lst.add(new int[] { x, y + 1 });
			}
		}
		return lst;
	}

	public static int[] BFS(int[] start, char[][] board) {
		boolean[][] v = new boolean[N][M];
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		v[start[0]][start[1]] = true;
		while (!q.isEmpty()) {
			int[] now = q.poll();
			for (int[] next : moveNext(now[0], now[1], board)) {
				if (v[next[0]][next[1]])
					continue;
				v[next[0]][next[1]] = true;
				q.add(next);
				if (board[next[0]][next[1]] == '.') {
					return next;
				}

			}
		}
		return start;
	}

}