가스관 [백준 2931][JAVA][골드 3][DFS]

 

[광고 누르면 오늘의 행운 상승!!]

https://www.acmicpc.net/problem/2931

2931번: 가스관

1. 참고사항

코드가 길어질 수 밖에 없는 더러운 문제

2. 구현

- 파이프를 받으면 4방향 boolean배열을 이용하여 연결 가능한 곳을 true로 바꿔주었다.
- 시작점부터 DFS를 진행하여 파이프가 이어져 있는데 '.' 를 만난다면 그곳은 해커가 훔쳐간 자리
- 해커가 훔쳐간 자리를 4방향으로 탐색하여 파이프 모양을 유추한다.
- M와 Z도 4방향 처리를 해 주었기 때문에 if문을 통해 잘 걸러주어야 한다. (가스의 흐름은 유일해야 하므로)

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

public class Main {
	
	static int dx[] = {-1,0,1,0};
	static int dy[] = {0,1,0,-1};
	static char gas[] = {'|', '-', '+', '1', '2', '3', '4'};
	static char[][] map;
	static boolean[][][] pipe;
	static int SROW,SCOL,R,C,N;
	static int[] dir = new int[4];
	
	public static void main(String[] args) throws Exception {
		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];
		pipe  = new boolean[4][R][C];
		
		for (int i = 0; i < R; i++) {
			char ch[] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = ch[j];
				if(map[i][j] != '.') {
					//파이프 방향대로 true로 바꿔줌
					checkPipe(i, j,true);
				}
				if(map[i][j] == 'M') {
					SROW = i;
					SCOL = j;
				}
			}
		}
		dfs(SROW,SCOL);
	
	}
	private static void checkPipe(int i, int j, boolean flag) {
		switch (map[i][j]) {
		case '|': 
			pipe[0][i][j] = flag;
			pipe[2][i][j] = flag;
			break;
		case '-': 
			pipe[1][i][j] = flag;
			pipe[3][i][j] = flag;
			break;
		case '1': 
			pipe[1][i][j] = flag;
			pipe[2][i][j] = flag;
			break;
		case '2': 
			pipe[0][i][j] = flag;
			pipe[1][i][j] = flag;
			break;
		case '3': 
			pipe[0][i][j] = flag;
			pipe[3][i][j] = flag;
			break;
		case '4': 
			pipe[2][i][j] = flag;
			pipe[3][i][j] = flag;
			break;
		case 'M':
			pipe[0][i][j] = flag;
			pipe[1][i][j] = flag;
			pipe[2][i][j] = flag;
			pipe[3][i][j] = flag;
			break;
		case 'Z': 
			pipe[0][i][j] = flag;
			pipe[1][i][j] = flag;
			pipe[2][i][j] = flag;
			pipe[3][i][j] = flag;
			break;
		case '+': 
			pipe[0][i][j] = flag;
			pipe[1][i][j] = flag;
			pipe[2][i][j] = flag;
			pipe[3][i][j] = flag;
			break;
		}
		
	}
	private static void dfs(int row, int col) {
		for (int i = 0; i < 4; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			//선넘음
			if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			
			//앞이 비어있는데 연결하는 파이프가 있는경우(해커가 훔쳐간 곳)
			if(map[nx][ny] == '.' && pipe[i][row][col]
					&& map[row][col] != 'M' && map[row][col] != 'Z') {
				
				//4방향 탐색 하면서 이어질 수 있는 파이프를 찾는다.
				for (int p = 0; p < 4; p++) {
					int pnx = nx + dx[p];
					int pny = ny + dy[p];
					//선넘음
					if(pnx < 0 || pnx >= R || pny < 0 || pny >= C) continue;
					//모스크바와 지그레브가 아닐 때
					if(map[pnx][pny] == 'M' || map[pnx][pny] == 'Z') continue;
					//해당 방향의 파이프 ++
					if(pipe[(p+2)%4][pnx][pny]) dir[p]++;
				}
				
				findPipe(nx,ny);
			}
			//그저 빈곳일 때
			else if(map[nx][ny] == '.') continue;
			
			//파이프가 이어질 수 있을 때
			if(pipe[i][row][col] && pipe[(i+2)%4][nx][ny]) {
				//파이프 사용 불가능
				pipe[i][row][col] = false;
				pipe[(i+2)%4][nx][ny] = false;
				dfs(nx,ny);
				//파이프 사용 가능
				pipe[i][row][col] = true;
				pipe[(i+2)%4][nx][ny] = true;
			}
		}
	}
	private static void findPipe(int row , int col) {
		char ch = 'n';
		if(dir[0] == 1 && dir[1] == 1 &&
				dir[2] == 1 && dir[3] == 1) ch = '+';
		else if(dir[0] == 1 && dir[2] == 1) ch = '|';
		else if(dir[1] == 1 && dir[3] == 1) ch = '-';
		else if(dir[1] == 1 && dir[2] == 1) ch = '1';
		else if(dir[0] == 1 && dir[1] == 1) ch = '2';
		else if(dir[0] == 1 && dir[3] == 1) ch = '3';
		else if(dir[2] == 1 && dir[3] == 1) ch = '4';

		System.out.println((row+1) + " " + (col+1) + " " + ch);
		System.exit(0);
	}
}