[백준] 3109 - 빵집 (JAVA)

1. 소요시간 : 15분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 2
4. 문제 유형 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 깊이 우선 탐색
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/3109
8. 푼 날짜 : 2023.03.16

1. 사용한 자료구조 & 알고리즘

dfs, 그리디 알고리즘을 사용했다.

2. 풀이과정

우선 어떤 방식이 그리디 알고리즘일까 생각해봤다. 내가 첫번째로 생각한 것은 우측으로 이동하되, (우측 위), (그냥 우측) , (우측 하단) 으로 나누면서,
(1) 우측 위로 이동할 수 있으면 바로 이동.
(2) 우측 위로 이동할 수 없다면 그냥 우측으로 이동
(3) 그냥 우측으로 이동할 수 없다면 우측 하단으로 이동
3가지 방식을 사용했다.

1. map [0,0] , [1,0] , [2,0] .... [n,0] 에서 각각 dfs 실행.
2. 앞서 말한 (1), (2) , (3) 의 조건으로 dfs 를 수행.
3. 만약 x 좌표가 우측 끝에 도착했다면 count를 증가
4. (여기서 중요) dfs에서 내가 현재 [0,0] 에서 출발한 것이 이미 count를 증가시켰다면, status라는 boolean 타입 변수를 true 로 만들어 준다. dfs가 1번 수행할 때 최대 3가지 방향으로 가지를 뻗어 나가므로 이때 이미 status 가 true 라면 더 이상 탐색해서는 안된다. 그러므로 status 가 true 라면 break 해준다.
5. 따라서 [0,0], [1,0], [2,0] 에서 dfs 를 수행시킬 때마다 status 를 false 로 바꿔준다.
   

3. 소스코드

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

public class Main {
	static char map[][];
	static boolean visited[][];
	static int yy[]= {-1,0,1};
	static int xx[]= {1,1,1};
	static int count=0;
	static boolean status=false;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int row=Integer.parseInt(st.nextToken());
		int col=Integer.parseInt(st.nextToken());
		
		map=new char[row][col];
		visited=new boolean[row][col];
		
		for(int i=0;i<row;i++) {
			String line=br.readLine();
			for(int j=0;j<line.length();j++) {
				map[i][j]=line.charAt(j);
			}
		}
		
		for(int i=0;i<map.length;i++) {
			status=false;
			dfs(i,0);
		}
		
		System.out.println(count);

		
	}
	public static void dfs(int y,int x) {
		visited[y][x]=true;
		if(x==map[0].length-1) {
			count++;
			status=true;
			return;
		}
		for(int i=0;i<3;i++) {
			int nextY=y+yy[i];
			int nextX=x+xx[i];
			if(status) break;
			if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length) continue;
			if(visited[nextY][nextX]==true ||map[nextY][nextX]=='x') continue;
			
			
			dfs(nextY,nextX);
			
		}
		
		
	}

}

4. 결과

5. 회고

확실히 나는 그래프 이론을 제일 잘한다.. ! 그래프 이론 문제는 골드 2여도 한 50~60 % 확률로 푸는데 다른 그리디 알고리즘은 골드 5여도 쉽게 못풀고 다이나믹 프로그래밍은 실버 문제도 못푸는게 많기도 하고 ... 그래고 골드 2 문제를 내 스스로 그것도 15분만에 풀었다니 뿌듯하다.
문제를 풀고 다른 사람 코드를 몇개 봤는데 432ms 면 굉장히 빠른 속도로 푼 케이스 였다 .

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212