hansjour 개발일지

문제 파악- 출발점 X에서 특정 거리 K가 걸리는 노드들을 체크하고 마지막에 출력해주기 -BFS 접근 방법-BFS사용해 최단 거리 카운트하기-출발점은 하나이고 단일로 연결 된 노드를 타고 가서 거리를 카운트-거리는 모두 1로 통일(별도의 가중치 없음 파악)-visited를 int[]로 변형 활용하여(토마토 문제처럼) 노드마다 '출발점에서 얼마나 걸렸는지' 적재해주기     코드 구현package org.server;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedRea..

문제 파악- 친구의 친구까지만 구하기 -완전 탐색 접근 방법-안전 영역이 '최대'가 되는 경우를 구해내기-단순 주어진 강수량 이하를 기준으로 dfs(완전탐색)하는 문제가 아님-모든 강수량의 case를 탐색해야 함    -탐색 범위는 지역 최대 높이까지(강수량 최대 case)   코드 구현package org.server;import java.io.*;import java.util.*;public class Main { static boolean[][] visited; static int[][] ground; static int N; public static void main(String[] args) throws IOException{ BufferedReader br =..

문제 파악- 친구의 친구까지만 구하기 -그래프 이론-그래프 탐색-너비 우선 탐색 접근 방법-특정 레벨까지만 탐색해야 하므로 완전탐색X BFS접근을 사용해야 한다.-'친구의 친구'까지라고 명시되어있기 때문에 lev2까지 탐색한다고 힌트를 얻을 수 있음  코드 구현package org.server;import java.io.*;import java.util.*;public class Main { static boolean[] visited; static int N; static Map> graph; static int cnt=0; public static void main(String[] args) throws IOException{ BufferedReader br =..

https://www.acmicpc.net/problem/5014 문제 파악- 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. - 첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.  -그래프 이론 -그래프 탐색 -너비 우선 탐색 접근 방법-최소시간을 구해 리턴해야 하므로 BFS접근을 사용-정수 배열을 담는 큐 자료형 사용-정수 배열에는 층x와 버튼을 누른 횟수가 담긴다.  코드 구현package com.baekjoon;public class p501..

https://www.acmicpc.net/problem/1697   문제 파악- 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.-그래프 이론 -그래프 탐색 -너비 우선 탐색 접근 방법-최소시간을 구해 리턴해야 하므로 BFS접근을 사용한다.-정수 배열을 담는 큐 자료형 사용-정수 배열에는 수빈이의 위치 x와 걸린 시간이 담긴다.  코드 구현package com.baekjoon;public class p1697_숨바꼭질 { public static int p1697_숨바꼭질() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(..

https://www.acmicpc.net/problem/2468    문제 파악-특정 강수량마다 잠기는 곳/안 잠기는 곳 구분하여 배열 저장- 안잠기는 곳을 '섬'이라 칭하자- dfs원리로 매 케이스의 섬을 카운트하여 가장 큰 카운트를 리턴 🎈[알고리즘 분류]그래프 이론브루트포스 알고리즘그래프 탐색너비 우선 탐색깊이 우선 탐색 접근 방법-BufferedReader와 StringTokenizer 이용해 값을 입력받기- BufferedReader는 처음에 선언하고 br.readLine()으로 받기- StringTokenizer는 한 줄단위로 쪼갤 때마다 선언..!, delimeter는 뒤에 적어주기, 실제 쪼갤 때는 st.nextToken() 사용-각 강수량마다 잠기는 지역/안잠기는 지역 비교문으로 fa..

https://www.acmicpc.net/problem/2606   문제 파악-컴퓨터가 이어져있으면 바이러스가 옮는다. 는 개념-저번에 파이썬으로 푼 문제 재풀이-한 네트워크에서 영향받는 컴퓨터 수 세는 것임 접근 방법-주어진 int끼리 연결하여 인접 리스트 먼저 만들고(양방향)해당 노드와 이어진 모든 노드 순회하며 카운트-visited와 count는 모두 멤버변수로 선언한다. 코드 구현import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class 바이러스 { static..

https://www.acmicpc.net/problem/2178 문제 파악-BFS를 이용해 최소 거리 구하기-1은 이동 가능한 거리, 0은 이동 불가능한 거리  접근 방법-(1,1)이 시작점이지만 좌표 상 0,0이므로 고려해서 풀기  코드 구현import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int answer=0; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(..

https://www.acmicpc.net/problem/2667  문제 파악-네트워크 문제와 비슷하게, 연결 된 집을 갯수를 모두 카운트하고-한 단지가 끝나면 다른 단지도 순회한다.-N X N 크기 접근 방법-DFS로 탐색(재귀 탐색)-탐색 후 visited 체크(혹은 0으로 변경?)-재귀 호출 일어날 때마다 cnt증가, 종료될 때마다 cnt합산-다른 집 옮겨갈 때 dfs 사용한다. (dfs 한번 당 1)-결과값은 재귀호출 내에서 관리하는 것이 아니라매 dfs마다 새로운 변수를 만들어 타고타고 누적하며 그 값을 리턴하면 1씩 누적되는 형태(모아서 바치는 형태로 생각하자.)-DFS함수는 int형태를 리턴하고, 한 단지의 순회가 끝나면 모아모아 받은 결과값을 메인함수에서 저장 코드 구현import java..

https://www.acmicpc.net/problem/2644   문제 파악-총 노드 갯수 n-특정 노드 a,b (a: start, b: target)-간선 m-~연결관계~ : 단방향(부모-자식 관계 명확)*StringTokenizer는 문자열 한 줄에서만 유효, 여러 줄일 시 새로운 st 선언해줘야 한다. *또한 띄어쓰기가 있는 문자열 쪼개는 데 쓴다.*br.readLine으로 받아서 해당 String.charAt()으로 받는 건 띄어쓰기가 없을 경우에 사용! 접근 방법-BFS함수 별도 작성-시작점a로부터 도착노드b까지 top-bottom이 명확한 그래프이지만, 위로 거슬러 올라가는 로직을 별도로 추가하여4방향 탐색하듯이 (경우 따져보고 전진), 가능하면 전진하여 카운트하고 아니면 그 다음 경우로 ..