고민의 흔적

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문제밖에 풀지 못하네요. 알고리즘 고수가 되는 그날까지 분발하겠습니다. 

숨바꼭질 1679번

내가 떠올린 풀이 해설

BFS를 응용해서 푸는 문제였다. BFS()를 호출한 후 BFS에서 arr 배열을 최대 크기 배열로 생성한 후 Queue에 n을 add한다. Queue가 비어있을 때까지 반복한다. now 값에 Queue에서 poll 한 값을 대입하고 for문을 i가 3보다 작을 때까지 반복한다. 1초 후에 now - 1, now + 1, now * 2로 움직여야한다. 만약 next가 k와 같다면 arr[now]를 리턴해준다. 또한 만약 next가 0보다 크거나 같고 next가 100001보다 작아야하고 arr[next]가 0일 때 arr[next]에 arr[now] + 1을 대입한다. 그리고 Queue에 next를 add한다.

정확한 풀이

import java.util.*;
public class Baek1697 {
	static int n;
	static int k;
	static int[] arr;
	static Queue<Integer> que = new LinkedList<>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		
		if (n >= k) {
            System.out.println(n - k);
        } else {
            System.out.println(BFS());
        }
	}
	private static int BFS() {
		arr = new int[100001];
		que.add(n);
		arr[n] = 1;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i = 0; i < 3; i++) {
				int next;
				if (i == 0) {
                    next = now - 1;
                } 
				else if (i == 1) {
                    next = now + 1;
                } 
                else {
                    next = now * 2;
                }
                if (next == k) {
                    return arr[now];
                }
                if (next >= 0 && next < 100001 && arr[next] == 0) {
                    arr[next] = arr[now] + 1;
                    que.add(next);
                }
			}
		}
		return 0;
	}
}

파티 1238번

내가 떠올린 풀이 해설

이 문제를 푸는데 시간이 오래 걸렸다. 다익스트라에서 조금만 응용하면 되는 문제였다. 1~N을 출발점으로 파티 마을 X까지의 거리를 다익스트라로 구한다. 그리고 반대로 파티 마을 X를 출발점으로 다익스트라를 돌려서 각 마을까지의 거리를 구했다. 그리고 이 두 값을 마을마다 더해주면 오고 가는 거리가 나오는데 이 값들 중 최댓값을 구하면 된다. time 배열은 파티 마을까지 오고 가는 거리의 값이다. 1~N 마을을 출발지로 다익스트라를 돌린 후 X까지의 거리를 time에 더해준다. 그 후 X를 출발지로 각 마을까지 거리를 구하여 time에 더해준다. 그 이후 time의 값들 중 최대값을 출력한다. 그 다음 dijkstra를 호출하고 다익스트라 메서드에서 우선순위 큐에 시작 정점을 넣어준다. 시작 지점의 가중치는 0이다. visit, distance를 초기화하고 distance에는 -1을 넣어준다. 우선순위 큐가 빌 때까지 while문을 반복한다. 현재 정점에 방문하지 않았을 때 연결된 정점들에 대해 검사를 시작한다. 연결된 정점의 가중치가 -1이거나 연결된 정점의 가중치가 현재 정점의 가중치와 현재 간선의 가중치의 합보다 클 때 값을 업데이트한다. 업데이트 후 다음 정점을 우선순위 큐에 넣어준다. Circle 클래스는 정점의 번호와 가중치를 가진다. 우선순위 큐의 타입으로 이용하기 위해 Comparable을 implements 해준다. 정렬 기준은 가중치의 오름차순이다.

참고 블로그

https://jellyinghead.tistory.com/79

정확한 풀이

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

public class Baek1238 {
	static int[] distance;
	static boolean[] visit;
	static ArrayList<Circle>[] list;
	static PriorityQueue<Circle> que = new PriorityQueue<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		visit = new boolean[n + 1];
		list = new ArrayList[n + 1];
		distance = new int[n + 1];
		
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<Circle>();
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			list[u].add(new Circle(v, w));
		}
		int time[] = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dijkstra(i);
            time[i] += distance[x];
        }
        
        dijkstra(x);
        for(int i = 1; i <= n; i++)
            time[i] += distance[i];
        
        int max = 0;
        for(int i = 1; i <= n; i++) 
            max = Math.max(max, time[i]);
    
        System.out.println(max);
	}

	private static void dijkstra(int x) {
		que.offer(new Circle(x, 0));
		visit = new boolean[visit.length];
		distance = new int[distance.length];
        Arrays.fill(distance, -1);
		distance[x] = 0;
		while(!que.isEmpty()) {
			Circle current = que.poll();
			int c_v = current.vertex;
			if(visit[c_v]) {
				continue;
			}
			visit[c_v] = true;
			for(int i = 0; i < list[c_v].size(); i++) {
				Circle tmp = list[c_v].get(i);
				int next = tmp.vertex;
				int value = tmp.value;
				if(distance[next] == -1 || distance[next] > distance[c_v] + value) {
					distance[next] = distance[c_v] + value;
					que.add(new Circle(next, distance[next]));
				}
			}
		}	
	}
}	
class Circle implements Comparable<Circle> {
	int vertex, value;
	Circle(int vertex, int value) {
		this.vertex = vertex;
		this.value = value;
	}
	@Override
	public int compareTo(Circle o) {
		return value - o.value;
	}
}

오늘의 회고

오늘은 BFS와 다익스트라 문제를 풀었습니다. 두 문제 모두 조금만 응용해서 푸는 문제였고, 너무 오랫만에 BFS와 다익스트라 문제를 풀어서 시간이 오래걸렸습니다. 다른 개념들도 까먹지않게 여러 개념의 문제들을 풀어야할 것 같습니다. 조금만 화이팅하자

BFS

너비 우선 탐색으로 그래프를 완전 탐색하는 알고리즘 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

BFS 핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

   BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.

   그래프를 인접 리스트로 표현하는 것이 역시 DFS와 동일하다.

2. 큐에서 노드를 꺼낸후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

   큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.

   이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.

   또한 큐에서 꺼낸 노드는 탐색 순서에 기록한다.

3. 큐 자료구조에 값이 없을 때까지 반복하기

   큐에 노드가 없을 때까지 앞의 과정을 반복한다.

코드 예시

static boolean visit[];   // 방문 배열 선언
static ArrayList<Integer>[] A;  // 인접리스트 선언

public static void BFS(int Node) {
	Queue<Integer> que = new LinkedList<Integer>();
    que.add(Node);
    visit[Node] = true;
    
    while(!que.isEmpty()) {
    	int now = que.poll();
        for(int i : A[now]) {
        	if(!visit[i]) {
            	visit[i] = true;
                que.add(i);
            }
        }
    }
}

시간 복잡도(노드 수 : V, 에지 수 : E)

 - 인접 리스트 = O(V+E)

 - 인접 행렬 = O(V^2)

36번 잃어버린 괄호

내가 떠올린 풀이 해설

가장 작은 최솟값을 만들기 위해서는 가능한 큰 수를 빼야 된다. 수식이 더하기 빼기로만 되어있기 때문에 더하기 부분에 괄호를 쳐서 먼저 모두 계산한 후 빼기를 실행한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1541 {
	static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String st = br.readLine();
		String []str = st.split("-");
		
		for(int i = 0; i < str.length; i++) {
			int tmp = mySum(str[i]);
			if(i == 0) {
				answer = answer + tmp;
			}
			else {
				answer = answer - tmp;
			}
		}
		System.out.println(answer);
	}
	private static int mySum(String a) {
		int sum = 0;
		String temp[] = a.split("[+]");
		for(int i = 0; i < temp.length; i++) {
			sum += Integer.parseInt(temp[i]);
		}
		return sum;
	}
}

46번 특정 거리의 도시 찾기

내가 떠올린 풀이 해설

모든 도로 거리가 1이므로 가중치 없는 인접리스트로 표현할 수 있다. 도시의 개수가 300,000, 도로의 최대 크기가 1,000,000이므로 BFS 탐색으로 해결할 수 있다. 최초에는 방문 도시가 1이고, 이동하지 않았으므로 방문 배열에 0을 저장한다. 이후 방문하는 도시는 이전 도시의 방문 배열 값 +1을 방문 배열에 저장한다. 탐색 종료 후 방문 배열에 값이 k와 같은 도시의 번호를 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek18352 {
	static int [] visit;
	static ArrayList<Integer>[] list;
	static List<Integer> answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n + 1];
		visit = new int[n + 1];
		answer = new ArrayList<>();
		
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			list[s].add(e);
		}
		for(int i = 1; i <= n; i++) {
			visit[i] = -1;
		}
		BFS(x);
		for(int i = 1; i <= n; i++) {
			if(visit[i] == k) {
				answer.add(i);
			}
		}
		if(answer.isEmpty()) {
			System.out.println(-1);
		}
		else {
			Collections.sort(answer);
			for(int b : answer) {
				System.out.println(b);
			}
		}
	}
	private static void BFS(int x) {
		Queue<Integer> que = new LinkedList<>();
		que.add(x);
		visit[x]++;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i : list[now]) {
				if(visit[i] == -1) {
					visit[i] = visit[now] + 1;
					que.add(i);
				}
				
			}
		}
		
	}
}

47번 효율적인 해킹

내가 떠올린 풀이 해설

모든 노드를 각각 BFS 탐색 알고리즘을 적용해 탐색한다. 탐색을 수행하면서 탐색되는 노드들의 신뢰도를 증가시켜 준다. 탐색 종료후 신뢰도 배열을 탐색해 신뢰도의 최댓값을 Max값으로 지정하고, 신뢰도 배열을 다시 탐색하면서 Max값을 가진 노드를 오름차순으로 출력한다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1325 {
	static int []answer;
	static ArrayList<Integer>[] list;
	static boolean []visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n + 1];
		visit = new boolean[n + 1];
		answer = new int [n + 1];
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			list[s].add(e);
		}
		for(int i = 1; i <= n; i++) {
			visit = new boolean[n + 1];
			BFS(i);
		}
		int max = 0;
		for(int i = 1; i <= n; i++) {
			max = Math.max(max, answer[i]);
		}
		for(int i = 1; i <= n; i++) {
			if(answer[i] == max) {
				System.out.print(i + " ");
			}
		}
 	}
	private static void BFS(int i) {
		Queue<Integer> que = new LinkedList<>();
		que.add(i);
		visit[i] = true;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int b : list[now]) {
				if(visit[b] == false) {
					visit[b] = true;
					answer[b]++;
					que.add(b);
				}
			}
 		}
	}
}

잘못된 풀이

import java.io.*;
import java.util.*;
public class Main {
	static int n, m;
	static ArrayList<Integer>[] list;
	static int []answer;
	static boolean []visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n + 1];
		answer = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list[x].add(y);
		}
		
		for(int i = 1; i <= n; i++) {
			visit = new boolean[n + 1];
			BFS(i);
		}
		int max = 0;
		for(int i = 1; i <= n; i++) {
			max = Math.max(max, answer[i]);
		}
		for(int i = 1; i <= n; i++) {
			if(answer[i] == max) {
				bw.write(i + " ");
			}
		}
		bw.flush();
		bw.close();
	}
	private static void BFS(int i) {
		Queue<Integer> que = new LinkedList<>();
		que.add(i);
		visit[i] = true;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int b : list[now]) {
				if(visit[b] == false) {
					answer[b]++;
					que.add(b);
				}
				
			}
		}
	}
}

문제점

이 문제에서 진짜 많이 해멧다 계속 시간 초과가 나는 것이었다. 정답이 된 코드와 잘못된 코드와 다른 게 없는데 계속 시간 초과가 났다. 문제를 모르겠다. 뒤에 정답 된 코드를 제출했더니 정답이 나왔다...

오늘의 회고

오늘은 그리디와 그래프 문제를 풀어봤습니다. 그래프 문제는 앞에서 배웠던 DFS, BFS를 활용해서 해결하는 문제였다. 앞에서 배웠지만 직접 구현하기에는 힘든 점이 있었습니다. 이번 주말 일요일에는 다른 공부 하지 않고 알고리즘만 복습하는 시간을 가지겠습니다. 알고리즘 공부를 시작한 지 얼마 안 되었기 때문에 지치지 않고 좌절하지 않고 풀어내는 힘을 길어내는 게 중요한 것 같습니다. 요행을 바라지 말고 정직하게 공부하자.