요르딩딩

이번문제는 가장 기본적인 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); // 출력(방문시만 출력*..

이번문제는 간단한 DFS로 풀수 있는 문제였습니다. 다만, 시간초과 이슈로 계속 틀려 찾아보고 여러가지 수정하여 정답이 맞았으나.. 맞은 정답의 원인을 찾고자 다시 맞은답을 실행해 보니... 틀렸다는... 무슨일인가... 원인을 어떻게 찾으란 밀인가.. 일단 내가 생각한 시간문제를 해결하는 방법을 적어보겠습니다. 1. Scanner 대신 BufferedReader, StringTokenizer 사용하기 2. public class Main 대신 class Main 사용하기 3. 불필요한 import문 제거 정도인것 같다. 이문제의 핵심 역시 dfs를 각 노드별로 반복해서 수행한다는 점이다. 그리고 감염되는 컴퓨터수를 조건에 맞게 증가하면 끝!!! 보다 명확한 시간초과문제 해결방법이 나오게되면 참고해봐야겠..

이번문제도 DFS를 사용하면 되는 문제입니다. 문제를 풀면서 주의해야 할점에 대해 적어보도록 하겠습니다. 입력하는 그래프가 양방향인지, 단방향 그래프인지 꼭!!! 확인해야한다. -> 양방향인줄 알고 조금 시간이...지체... 젠자..ㅇ 각, 시작점(i)/목표점(j)을 기준으로 두고 DFS를 반복적으로 한다. 단, 반복적으로 진행할때 방문배열은 초기화해야합니다. 목표에 도달하면, 플레그를 변경하여 도달확인 노드는 1번부터 시작하므로, 노드번호 주의 (모드 노드를 -1해서 생각하면 쉽다.) package com.controller; import java.util.*; public class Main { static int n; static boolean[] visited ; static ArrayList g..

가장 기본적인 DFS 문제인것 같습니다. 카운트, 무방향 간선, 인덱스 확인 이렇게 3가지 정도면 잘 확인하면 풀 수 있는 문제입니다. import java.util.*; public class Main { static int n,m; static boolean[] visited; //노드 수 만큼생성 static ArrayList graph = new ArrayList(); static int result = 0; public static void dfs(int now) { // DFS(재귀) visited[now] = true; //방문표시 for(int i =0; i< graph.get(now).size(); i++) { int tmp = graph.get(now).get(i); if(visited..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 나는 처음에 재귀를 통해서 문제를 풀었다. 재귀로 풀게된 이유는 해당 입력값을 각각 1, 2, 3으로 한번씩 빼고, 거기서 나온 값을 또 1, 2, 3을 뺴는 식으로 반복한 뒤, 마지막으로 0이 나온것들의 카운트를 세면 된다고 생각했기 때문이다. 4 - 1 =3 여기서 또 1 ,2, 3 각각 빼기 반복 4 - 2 =2 여기서 또 1 ,2, 3 각각 빼기 반복 4 - 3 =1 여기서 또 1 ,2, 3 각각 빼기 반복 그러면 DFS 모양과 비슷한 모습을 찾을 수 있었다. DFS는 스택함수를 기초로 ..

https://hidelookit.tistory.com/195 [백준 14890] 경사로 (자바) 백준 14890번 경사로 (자바) 출처 www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다.. hidelookit.tistory.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static int n, l; ..

이번문제는 문제를 이해하고, 어느정도 해결책까지는 접근할 수 있었으나, 아직 dfs(깊이우선탐색)에 대한 문제를 많이 풀어보지 않았기때문에, dfs관련 문제인지 파악하지 못했던거 같다. dfs는 자주 출제되는 문제유형이니 잘 공부하도록하자. 우선 처음 접근할때는 규칙을 찾으려고 노력했다. 하지만 모두 공통된 규칙을 찾기에는 쉽지 않았다. 찾아보니 dfs문제임을 알 수 있었다. 그 이유는 처음 한 조각을 고르면 4변에 붙일 수 있고, 붙이고 나면 그 다음블록에는 3변에 붙일 수 있고, 그 다음은 3블록 (4X3X3)이런식으로 붙일 수 있다는 규칙이 있었다. 하지만, 이게 왜 dfs인지 알아야한다. 처음 한칸을 시작으로 4가지 경우, 그리고 3가지 경우, 그리고 3가지 경우로 발생되며, 이때 나온 합들 중 ..

이번 문제는 나름 꽤 시간이 걸렸던 문제였습니다. 물론 시간날때마다 도전해서 그렇긴 하지만 String 문자를 char형으로 변환하여 증가/감소 시킬수 있다는 점과 변환하는 방법, 그리고 익숙하지만 잘 안쓰게 되는 swich문도 사용해 보았습니다. 1. 먼저 문제를 읽은 후 문제에 대한 이해가 중요합니다. 이번문제에서 헷갈렸던 부분은 돌을 언제 움직일 수 있느냐 였습니다. 문제를 보고 이해한 바로는 = 체스가 돌이 있는 위치로 이동하게 되면, 그 돌을 체스가 이동해온 방향으로 이동시킨다 였습니다. 문제를 풀어본 결과 다행이 제대로 이해한거 같습니다. 2. 이제 문제를 이해했으니, 규칙을 만드는 것이었습니다. 규칙을 만들어야 로직을 짤때 수월하기 때문입니다. 여기서 고민했던점은 "RT"로 이동할때 "R"로..