[java] 백준(BOJ) - 가스관

문제

백준-가스관
M에서 Z를 잇는 블록에서 지워진 블록 하나의 위치와 종류를 찾는 문제

• 제한 사항
  블록의 크기 R,C : 1 <= R,C <= 25
  M,Z는 한번만 주어진다
  항상 답이 존재하고 가스의 흐름이 유일한 경우만 주어진다
  M과 Z가 하나의 블록과 인접해 있는 입력만 주어진다
  불 필요한 블록이 존재하지 않는다

• 블록 종류
  

풀이

처음엔 블록의 이동경로를 따라 끊긴 부분에서 답을 찾으려고 했는데
하다보니 너무 복잡해지는 감이 있었다

map(R*C)의 크기가 크지 않고, 1개의 블록만 찾으면 되는 문제여서 그냥 다 돌렸다

입력받은 map을 반복해서 .인 경우 4방향(상,하,좌,우)를 탐색한다
이 때, 4방향 중 M,Z가 아니면서(블록이면서) 방향과 이어지는 cnt(갯수)를 구한다
cnt = 4이면 4방향을 이어야 하므로 +블록을 써야한다
cnt = 2이면 두 방향을 이어 줄 수 있는 블록을 찾는다

상세 설명

코드 작성내용으로 설명하자면,
각 블록이 연결되어있는 방향을 표로 정리하면 다음과 같다

블록	상	하	좌	우
ㅣ	O	O	X	X
-	X	X	O	O
+	O	O	O	O
1(┌)	X	O	X	O
2(└)	O	X	X	O
3(┘)	O	X	O	X
4(┐)	X	O	O	X

.이 있는 칸에서 4방향을 탐색한다
북쪽(상)방향에 블록이 있는지 확인한다
블록이 있다면, 북쪽의 반대방향인 남쪽(하)방향과 연결되어있는지 확인한다
연결되어있다면 cnt를 증가시킨다

예시
M	ㅡ	❔
.	.	ㅣ
.	.	Z

• ❔에서 4방향을 탐색한다

  상 : 범위가 아니므로 x
  하 : | 블록이다. ‘|’블록은 반대방향인 ‘상’과 연결되어있으므로 cnt++
  좌 : ㅡ 블록이다. ‘ㅡ’블록은 반대방향인 ‘우’과 연결되어있으므로 cnt++
  우 : 범위가 아니므로 x

이 때 연결된 부분은 [하, 좌] 방향이다
[표]에서 [하, 좌]부분이 O인 블록은 4(┐)이므로 해당 블록이 답이된다

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class b2931_가스관 {

	private static char[][] map;
	private static int R;
	private static int C;
	private static int dx[] = { -1, 1, 0, 0 };
	private static int dy[] = { 0, 0, -1, 1 };
	private static Map<Character, Integer> idx; // 블록과 conn의 인덱스를 연결하기 위한 map
	static boolean[][] conn = { { true, true, false, false }, { false, false, true, true }, { true, true, true, true },
			{ false, true, false, true }, { true, false, false, true }, { true, false, true, false },
			{ false, true, true, false } };

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

		for (int i = 0; i < R; i++) {
			String t = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = t.charAt(j);
			}
		}
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] == '.') { // . 인 경우
					boolean[] re = new boolean[4];
					int cnt = 0;
					for (int k = 0; k < 4; k++) { // 4방향 탐색
						int nx = i + dx[k];
						int ny = j + dy[k];
						if (nx > -1 && ny > -1 && nx < R && ny < C && map[nx][ny] != '.' && map[nx][ny] != 'Z'
								&& map[nx][ny] != 'M' && conn[idx.get(map[nx][ny])][getOpp(k)]) { // 해당방향의 블록과 연결 시
							cnt++;
							re[k] = true;
						}
					}
					if (cnt == 4) { // 4방향 다 연결이면 +블록
						System.out.println((i + 1) + " " + (j + 1) + " +");
						return;
					} else if (cnt == 2) { // 2개 연결 시 
						printResult(i + 1, j + 1, re);
						return;
					}
				}
			}
		}
		// end
	}

	private static void printResult(int x, int y, boolean[] re) {
		// conn과 인접한 방향(re)를 비교
		for (int i = 0; i < conn.length; i++) {
			if (i == 2)
				continue;
			boolean flag = true;
			for (int j = 0; j < 4; j++) {
				if (conn[i][j] != re[j]) {
					flag = false;
					break;
				}
			}
			if (flag) {
				System.out.println(x + " " + y + " " + Origin(i));
			}
		}

	}

	private static char Origin(int i) {
		// map을 다시 블록으로 변환
		switch (i) {
		case 0:
			return '|';
		case 1:
			return '-';
		case 2:
			return '+';
		case 3:
			return '1';
		case 4:
			return '2';
		case 5:
			return '3';
		case 6:
			return '4';
		}
		return 0;
	}

	private static int getOpp(int d) { // 반대방향
		switch (d) {
		case 0:
			return 1;
		case 1:
			return 0;
		case 2:
			return 3;
		case 3:
			return 2;
		}
		return d;
	}

	private static void initIdx() {
		idx = new HashMap<>();
		idx.put('|', 0);
		idx.put('-', 1);
		idx.put('+', 2);
		idx.put('1', 3);
		idx.put('2', 4);
		idx.put('3', 5);
		idx.put('4', 6);
	}
}