[Unsolved][JAVA] 백준 3109 빵집

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

3109번: 빵집

 

1. 서론

 

골드2 치고는 그렇게 어렵지 않으나,, 난 답을 보는 순간까지도 문제를 제대로 이해하지 못했던 문제... ㅎ

 

2. 문제 풀이

 

가장 왼쪽 열에서 출발해서 가장 오른쪽 열에 도착할 때까지 파이프를 연결한다. 파이프는 현 위치에서 오른쪽, 오른쪽 대각선 위와 아래 세 군데만 설치 가능한다. 그러나 탐색 중 건물이 있는 경우에는 파이프를 연결할 수 없다. 가장 왼쪽 열에서 파이프를 연결해서 가장 오른쪽 열에 가는 동안 최대로 설치할 수 있는 파이프의 값을 구하는 문제이다. 

 

처음에는 열에서 출발하는 게 뭐지? 0,0에서 n - 1, n - 1 말하는 건가? 파이프는 또 어떻게 연결한다는 거지? 예제는 무슨 경우지? 모든 게 이해가 안 가서 인터넷에 검색해봤다. 그래서 열에서 출발하는 게 무슨 의미인지 알게 되었다.

 

그리고는 그냥 왼쪽 열 0번부터 n번까지 출발해서 도착하는 경우 중 파이프의 개수가 가장 많은 걸 출력하면 되겠다 생각했는데 그렇게 구현하고 나니까 테스트 케이스는 맞았는데 문제에서는 8%만 맞고 틀렸다고 나왔다.

 

나는 결국 인터넷을 찾아볼 수밖에 없었다. 

 

https://cocoon1787.tistory.com/399

[C/C++] 백준 3109번 - 빵집

 

그나마 내가 생각한 것과 가장 아이디어가 비슷한 코드이다.

오른쪽에서 왼쪽으로 탐색하기 때문에 ↗,→,↘ 순서대로 탐색하게 해 줬다. (순서가 틀리면 답도 틀린다. ↗ 이 방향을 → 보다 나중에 탐색하면 값을 그냥 지나칠 수 있기 때문이라고...)

배열을 탐색하면서 가장 왼쪽에서 오른쪽에 도착할 때까지 종료 조건 없이 계속 돌고 가장 오른쪽 인덱스에 도착하면 카운트를 센 후에 그 방향으로는 더 이상 탐색 안 하도록 return 해준다. 이렇게 계속 카운트를 세다 보면 가장 많은 파이프를 쓰고 도착하는 경우가 된다.

(앞에서 파이프를 적게 쓰는 방법은 모두 return 하고 멈추고 계속 탐색을 진행했기 때문에)

근데 인터넷에 찾아보다 안 건데 옛날에는 그림 힌트가 있었고 테케가 1개였는데 지금은 힌트가 사라지고 테케가 두 개가 됐네...

힌트 하나 없어졌다고 이해하기가 훨씬 어려워졌다 ㅠ

 

3. 코드 설명

 

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

public class Main {
	
	static char[][] map;
	static boolean[][] visit;
	static int n, m, cnt;
	static int[] dx = {-1, 0, 1}, dy = {1, 1, 1};
	static boolean check;
 	
	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());
		
		map = new char[n][m];
		
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) 
				map[i][j] = s.charAt(j);
		}
	
		visit = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			check = false;
			dfs(i, 0);
		}
		
		System.out.println(cnt);	
	}	
	
	public static void dfs(int x, int y) {
		visit[x][y] = true;
		
		if (y == m - 1) {
			cnt++;
			check = true;
			return;
		}

		for (int i = 0; i < 3; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (map[nx][ny] == '.' && !visit[nx][ny]) {
					dfs(nx, ny);
					if (check) return;
				}
			}
		}
	}
}

 

처음엔 참고만 하려고 했는데 결국엔 아예 똑같은 코드가 되어 버렸다.... ㅎ

 

값들을 입력받고 탐색하는데 열의 어디든지 출발해도 되기 때문에 dfs를 n번 반복해줬다.

dfs함수로 들어와서 방문 체크를 해주면서 ↗,→,↘ 세 방향을 탐색하고 도착하면 그 방향은 탐색을 멈추게 하고 남은 방향은 계속 탐색하게 했다.
check로 탐색을 구분해준다.

코드만 보면 도착하는 횟수를 세는 것 같이 보이는데... 그게 최대 파이프의 수가 된다니 신기하다....
(아직 100% 잘 모르겠음 ㅎ)