요르딩딩

이번문제는 쉬운듯 하면서도 어렵게 느껴졌던 문제이다. 그이유는 아무래도 익숙하지 않아서 그런것 같다. 처음에 2차원 배열말고, 1차원 배열로 적용하자니 왼쪽 위, 오른쪽 위의 인덱스를 찾아서 더해주는 부분을 구현하는데 애를 먹었다. 검색을 해보니 2차원 배열을 이용하는 내용이 있어, 참고 할 수 있었다. import java.util.*; class Main { static int n, result = 0; static int[][] dp; public static void dp() { for (int i = 1; i < n; i++) { // dp[0][0] 제외 for (int j = 0; j

이번문제 역시 각 노드별 BFS를 수행해나가면서 거리값을 갱신해 주는것이 핵심이다. 1번(나)로 부터 얼마만큼 떨어져있는지 알면, 친구인지 친구의 친구인지 알수 있기 때문이다. if (visited[tmp] == false) { // 아직방문전 dist[tmp] = dist[now] + 1; // 친구 관계 계산***** visited[tmp] = true; //방문표시 q.offer(tmp); } import java.util.*; class Main { static int n, m, start, end, resultCnt; static boolean[] visited; static int[] dist; static ArrayList graph = new ArrayList(); public static..

이번문제는 촌수 계산만 잘 적용하면, 기존 BFS 문제들과 비슷하다고 볼 수 있다. if(visited[tmp] == false) { //아직방문전 dist[tmp] = dist[now]+1; // 촌수 계산 dfs(tmp, end); //재귀 } import java.util.*; class Main { static int n, m, start, end; static boolean[] visited; static int[] dist; static ArrayList graph = new ArrayList(); public static void dfs(int now, int end) { visited[now] = true; //방문표시 for(int i=0; i< graph.get(now).size(); ..

이번문제는 BFS 문제이다. 처음 문제를 읽었을때는 BFS문제 인가 긴가민가 했었다. 다른사람들의 풀이를 보니 플로이드와샬 알고리즘으로 푼 케이스도 있었다. 이번 문제가 조금 어렵게 느껴졌던 이유는 그래프 자체를 노드로 구성했다는 점, 그리고 모든 노드를 방문할 수 있다고 가정한다는 점이 새롭고 낯설게 느껴졌다. 비록 반례나 풀이를 조금 참고하기는 했지만, 큰 틀은 기존 BFS와 별 차이가 없음을 느낄 수 있었다. 역시 다양한 경험이 중요하다는 점을 다시한번 깨달았다. import java.util.*; class Node { private int x; private int y; public Node(int x, int y) { this.x = x; this.y = y; } public int getX(..

이번문제는 조금 까다로운 문제인거 같다. 처음에 문제를 잘못 이해하는 바람에 헤메는 부분이 있었지만, 이내 잘 이해해서 풀 수 있었다. 또 이 문제는 BFS를 구현하기 보다는 BFS를 높이에따라 반복적으로 실행하여 영역을 계산해내는것이 주요한 문제인것 같다. 이번문제에서 주의해야 할점에 대해 이야기 해보도록 하겠다. 1. 물에 잠기는 부분과 안잠기는 부분 구분하기 2. 0~ 최대높이까지 BFS 반복하여 실행하기 1. 방문그래프 매번 초기화하기 import java.util.*; class Node { private int x; private int y; public Node(int x, int y) { this.x = x; this.y = y; } public int getX() { return this..

이번 문제는 행렬을 이용한 기본적인 BFS문제인거 같다. 여기서 주의할 점은 크게 없지만, 방문 그래프, 거리 그래프, 입력값 그래프 이렇게 세개의 그래프를 이용한다는 점만 주의하면 될거 같다. import java.util.*; class Node{ private int x; private int y; public Node(int x, int y) { this.x = x; this.y = y; } public int getX() { return this.x; } public int getY() { return this.y; } } class Main{ static int n,m; static boolean[][] visited; static int[][] dist; static int[][] graph..

이문제는 7569(토마토/3차원배열)를 푼 다음에 풀었기때문에 쉽게 풀수 있었다. 3차원 배열이었던것을 단순하게 2차원으로만 수정해주면 끝!!! import java.util.*; class Node { private int x; private int y; public Node(int x, int y) { this.x = x; this.y = y; } public int getX() { return this.x; } public int getY() { return this.y; } } class Main { static int n, m, resultCnt = 0; static boolean[][] visited = new boolean[n][m]; static int[][] day = new int[n]..

이번문제는 풀면서 꽤나 애먹었던 문제이다. 이문제를 풀면서 주의해야할 점에 대해 알아보기로 하자. 1. 3차원 배열 2. Node에서 변수 선언시 static 사용하지 않기 -> 변수가 공유되면 안됨. 3. 시작점이 여러개인 경우 Queue를 static으로 선언하고, 여러개의 시작점을 큐에 삽입 후 BFS 실행한다. 4. 그래프, 방문그래프, 날짜그래프 총 3개의 그래프를 이용한다. 1,3번의 경우 처음 접해보는 방식이기에 풀고나서 한층 더 보는 눈높이가 높아진거 같아서 기쁘다. package com.controller; import java.util.*; class Node { private int h; //static안붙이도록 주의***** private int x; private int y; pu..