요르딩딩

이번문제는 촌수 계산만 잘 적용하면, 기존 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..

이번문제는 사이클 개수를 구하는 문제이다. 이는 DFS를 이용하여 자기자신이 나오면 사이클인것으로 간주하기로 했다. 여기서 주의할 점은 방문하지 않은 노드들을 기준으로 DFS를 거쳐 사이클 유무를 판단해야한다는거다. 방문한 노드들은 이미 전 사이클에 포함되는 노드이므로, 방문하지 않은 노드들에 대해서만 DFS(사이클 판별)를 거치도록한다. 1,3,5,7은 하나의 사이클이므로 첫 DFS에서 모두 방문 처리돼있다. 방문하지않은 2를 기준으로 DFS(사이클 판별) 한다. 방문하지 않은 4 ... (반복) import java.util.*; /* * 자기자신이 나오면 사이클 완성 */ class Main { static int n, nodeCnt, start2, resultCnt; static boolean[]..

이번문제는 가장 기본적인 DFS와 BFS문제인거 같다. 여기서 주의해야 할점은 1. 방문할 수 있는 노드가 여러개이면, 작은 노드부터 방문한다 -> 정렬필요 2. 노드를 순서대로 출력 -> 방문표시시 출력한다. 3. DFS는 방문처리 1번, BFS는 방문처리 2번 import java.util.*; class Main { static int n, m, s; static boolean[] visited; static ArrayList graph; static ArrayList dfsList; static ArrayList bfsList; public static void dfs(int now) { visited[now] = true; // 방문표시 dfsList.add(now); // 출력(방문시만 출력*..