고민의 흔적

step 2 - 3. 올바른 괄호의 개수

내가 떠올린 풀이 해설

괄호를 보고 stack을 이용해서 풀려고 했는데 괄호 문자를 입력으로 주지 않아 DFS의 성질을 이용해 풀었다. 올바른 괄호의 짝 중에, '('로 시작했으면 ')'로 끝나는 성질을 이용해 ')'의 개수가 '('보다 많으면 올바르지 않은 식으로 간주하고, 이 모든 경우의 수를 dfs로 찾았다.

https://tosuccess.tistory.com/173

정확한 풀이

import java.util.*;
public class step2_3 {
	static int answer;
	public static void main(String[] args) {
		int n = 2;
		answer = 0;
		DFS(0, 0, n);
		System.out.println(answer);
	}
	private static void DFS(int left, int right, int n) {
		if(left < right) {
			return;
		}
		if(left == n && right == n) {
			answer++;
			return;
		}
		if(left > n || right > n) {
			return;
		}
		DFS(left + 1, right, n);
		DFS(left, right + 1, n);
	}
}

오늘의 회고

오늘은 프로그래머스 3주 차 문제를 풀었습니다. DFS를 이용해서 푸는 문제였다. DFS 문제라고 떠올리기는 했지만 문제를 해결하는 방법의 아이디어가 떠오르지 않았다... 좀 더 넓은 방식으로 문제를 해결해야 되는데 어떻게 공부해야 될지 잘 모르겠다.ㅠㅠ

step 2 - 2. 게임 맵 최단거리

내가 떠올린 풀이 해설

DFS로 풀어도 답이 나오는 문제인데 저는 BFS로 풀었습니다. dx, dy로 상하좌우를 탐색할 배열을 만들어 준다. 또한 visit 배열을 만들어준다. visit배열은 BFS를 탐색하면서 거리가 1씩 늘어날수록 이동한 거리를 담아 줄 배열이다. 만약 answer가 0이면 -1, 아니면 answer를 리턴해준다. BFS 메서드에서는 BFS를 이용할 Queue를 생성하고 시작점인 0,0을 배열로 Queue에 add 해준다. Queue가 빌 때까지 반복한다. for문으로 상하좌우를 탐색하면서 만약 nx, ny가 0보다 같거나 크고, nx, ny가 map길이보다 작아야 하고, maps배열의 nx, ny위치가 1이고, visit배열의 nx, ny가 0이면 visit [nx][ny]에 visit [x][y] + 1 값을 넣어준다. 그리고 Queue에 nx, ny를 add 해준다.

정확한 풀이

import java.util.*;
public class step2_2 {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int answer;
    static int[][] visit;
	public static void main(String[] args) {
		int [][]maps = {{1, 0, 1, 1, 1},
				{1, 0, 1, 0, 1},
				{1, 0, 1, 1, 1},
				{1, 1, 1, 0, 1,},
				{0, 0, 0, 0, 1}};
		answer = 0;
		int [][] visit = new int[maps.length][maps[0].length];
		visit[0][0] = 1;
		BFS(maps, visit);  
		answer = visit[maps.length - 1][maps[0].length - 1];
		if(answer == 0) {
			System.out.println(-1);
		}
		System.out.println(answer);
	}
	private static void BFS(int[][] maps, int[][] visit) {
		Queue<int[]> que = new LinkedList<>();
		que.add(new int[] {0, 0});
		while(!que.isEmpty()) {
			int[] now = que.poll();
			int x = now[0];
			int y = now[1];
			for(int i = 0; i < 4; i++) {
				int nx = dx[i] + x;
				int ny = dy[i] + y;
				if(nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length && maps[nx][ny] == 1 && visit[nx][ny] == 0) {
					visit[nx][ny] = visit[x][y] + 1;
					que.add(new int[] {nx, ny});
				}
			}
		}
    }
}

오늘의 회고

요즘 계속 알고리즘 문제를 1문제밖에 풀지 못하네요. 알고리즘 고수가 되는 그날까지 분발하겠습니다.