[백준 - 2931] 골드3 - 가스관 (구현)

1. 유형

구현, dfs

 

2. 풀이

1) M부터 4방 탐색

2) 가스관 별로 방향을 바꾼다

3) '.' 이 나왔을 때, 7가지의 가스관을 다 넣어본다

4) 탐색한 가스관의 갯수가 필요한 가스관의 수하고 같다면 종료한다

 

 

M부터 4방향을 탐색해서 시작 방향을 정한다.

 

현재 좌표에서 가스관의 종류별로 방향을 바꿔줘야 한다.

다음 좌표가 '.'이면 7가지의 가스관을 넣어서 완전 탐색한다

 

예외적으로 생각해야할 점은, 밑에 파란색 칸은 두번 세어주면 안된다.

그렇기 때문에 아래와 같은 코드가 필요하다.

방문한 지점이라면 cnt증가가 없다.

미방문 지점은 cnt+1을 한다

 

3. 코드

package 구현;

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

public class Baek_2931가스관 {
	static int N, M;
	static char map[][];
	static int dr[] = {-1,0,1,0};
	static int dc[] = {0,1,0,-1};
	static int ansR,ansC,tmpr,tmpc;
	static char ansType;
	static int K=0;
	static boolean visit[][];
	static char arr[] = {' ','|','-','+','1','2','3','4'};
	static boolean flag=false;
	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());
		M=Integer.valueOf(st.nextToken());
		map = new char[N][M];
		visit = new boolean[N][M];
		int startR=0, startC=0;
		for(int i=0; i<N; i++) {
			String str=in.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j]=='M') {
					startR=i;
					startC=j;
				}
				if(map[i][j]!='Z' && map[i][j]!='M' && map[i][j]!='.') {
					K++;
				}
			}
		}
		K++;
		for(int i=0; i<4; i++) {
			int nr = startR+dr[i];
			int nc = startC+dc[i];
			if(nr<0 || nr>=N | nc<0 ||nc>=M) continue;
			dfs(nr, nc, i, 0, true);
		}
		ansR+=1;
		ansC+=1;
		System.out.println(ansR+" "+ansC+" "+ansType);
	}
	static void dfs(int r, int c, int d, int cnt, boolean use) {
		if(flag) return;
		if(cnt==K) {
			ansR=tmpr;
			ansC=tmpc;
			ansType=map[ansR][ansC];
			flag = true;
			return;
		}
		int nd = change(d, map[r][c]);
		if(nd==-1) return;
		int nr = r+dr[nd];
		int nc = c+dc[nd];
		if(nr<0 || nr>=N | nc<0 ||nc>=M) return;
		if(map[nr][nc]=='.') {
			if(use==true) {
				//1~7까지 구하기
				for(int i=1; i<8; i++) {
					tmpr=nr; tmpc=nc;
					map[nr][nc] = arr[i];
					visit[nr][nc] = true;
					dfs(nr, nc, nd, cnt+1, false);
					map[nr][nc] ='.';
					visit[nr][nc] = false;
				}
			}
		}else {
			if(visit[nr][nc]) {
				dfs(nr, nc, nd, cnt, use);
			}else {
				visit[nr][nc] = true;
				dfs(nr, nc, nd, cnt+1, use);
				visit[nr][nc] = false;
			}
		}
	}
	
	static int change(int d, char pipe) {
		if(pipe=='|') {
			if(d==0 || d==2) return d;
		}else if(pipe =='-') {
			 if(d==1 || d==3) return d;
		}else if(pipe =='+') {
			return d;
		}else if(pipe=='1') {
			if(d==3) return 2;
			if(d==0) return 1;
		}else if(pipe=='2') {
			if(d==2) return 1;
			if(d==3) return 0;
		}else if(pipe=='3') {
			if(d==1) return 0;
			if(d==2) return 3;
		}else if(pipe=='4') {
			if(d==1) return 2;
			if(d==0) return 3;
		}
		return -1;	
	}
}