[백준] 3109번 : 빵집 - 자바(JAVA)

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

3109번: 빵집

 

문제 해석

첫째 열은 근처 빵집의 가스관 마지막 열은 원웅이의 빵집
건물을 피해서 가스관을 최대로 연결하고자 함
가스관은 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래로 이동 가능
각 칸의 중심끼리 연결
파이프라인은 서로 겹칠 수 없음

 

 

문제 풀이 전 설계

0번째 행렬의 0번째 row부터 N-1번째 row까지 순차적으로 파이프탐색

 

파이프 이동의 우선순위

1. 오른쪽 위

2. 오른쪽

3. 오른쪽 아래

 

 

코드

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

public class Main_3109_빵집 {

	static char[][] board;
	static boolean[][] visited;
	static int R, C, pipeLineCount;
	static int[] dy = { -1, 0, 1 };
	static final int DIRECTION = 3;
	static boolean finish;
    
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		board = new char[R][C];
		visited = new boolean[R][C];

		for (int y = 0; y < R; y++) {
			String temp = br.readLine();
			for (int x = 0; x < C; x++) {
				board[y][x] = temp.charAt(x);
				if (board[y][x] == 'x') {
					visited[y][x] = true;
				}
			}
		}

		for (int y = 0; y < R; y++) {
			finish = false;
			visited[y][0] = true;
			searchPipeLine(y, 0);
		}
		System.out.println(pipeLineCount);
	}

	static void searchPipeLine(int y, int x) {
		if (x == C - 1) {
			finish = true;
			pipeLineCount++;
			return;
		}

		for (int k = 0; k < DIRECTION; k++) {
			int tempY = y + dy[k];
			int tempX = x + 1;
			if (!isCoordValid(tempY, tempX)) {
				continue;
			}
			if (!isGo(tempY, tempX)) {				
				continue;
			}
			visited[tempY][tempX] = true;
			searchPipeLine(tempY, tempX);
			if(finish) {
				break;
			}
		}

	}

	static boolean isCoordValid(int tempY, int tempX) {
		// x,y 좌표의 범위 유효성 검사
		return (tempY >= 0 && tempX >= 0 && tempY < R && tempX < C);
	}

	static boolean isGo(int tempY, int tempX) {
		// visited배열이 false라면 갈수있음!
		return (!visited[tempY][tempX]);
	}

}