hansjour 개발일지

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..

문제 파악-저번 실습으로 나온 문제. 각 방을 돌며 최초의 좌석 찾고 그로부터 되는 방향을 나아가며 거리가 2 이내에 좌석이 발견되면 false리턴places의 행 길이(대기실 개수) = 5places의 각 행은 하나의 대기실 구조를 나타냅니다.places의 열 길이(대기실 세로 길이) = 5places의 원소는 P,O,X로 이루어진 문자열입니다.places 원소의 길이(대기실 가로 길이) = 5P는 응시자가 앉아있는 자리를 의미합니다.O는 빈 테이블을 의미합니다.X는 파티션을 의미합니다.입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.return 값 형식1차원 정수 배열에 5개의 원소를 담아서 return 합니다.places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로..

문제 파악-주어진 2차원 배열은 서로 간선으로 연결 된 관계-주어진 그래프에서 최대 거리에 있는 노드 갯수를 구하기노드의 개수 n은 2 이상 20,000 이하입니다.간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.접근 방법💡 -각 노드와 연결관계를 파악하고 인접리스트 형태로 변환하여 진행-bfs 를 이용하여 해당 그래프의 순회 거리를 구하고 최대 거리의 노드 갯수 구하기-방문 노드는 제외하고 큐 순회를 한다.-간선 별로 몇번 째로 순회하는지 세기 위한 cnt와 직관적으로 보기 편한 리스트 구현하기 코드 구현import java.util.*;class Solution { public ..

문제 파악-서로 이어져있는 그래프의 간선을 ‘하나’ 끊었을 때, 두 개로 나누어진 그래프를 각각 순회-순회 시 방문 노드를 카운트하여 리턴하고, 각 순회가 끝났을 때 두 그룹의 카운트 차를 비교-최솟값을 갱신하여 최종 리턴n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.1 ≤ v1 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.접근 방법💡 -BFS를 이용하여 각 노드를 순회 -그래프를 둘로 쪼갤 때 ⇒ 간선을 순회하며 하나씩 다 삭제해보기(O(n))-인접리스트 형태로 ..

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/1260 문제 파악-그래프를 DFS 혹은 BFS 형태로 순회하기 접근 방법-주어진 연결 정보를 인접 리스트 형태로 변환하여 그래프로 만들기-각각 DFS,BFS 함수를 만들기-결과값을 출력 코드 구현import java.util.*;public class Main { static boolean visited[]; static ArrayList[] A;//연결리스트로 구성된 Int형 배열 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(..

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방향 탐색하듯이 (경우 따져보고 전진), 가능하면 전진하여 카운트하고 아니면 그 다음 경우로 ..

https://leetcode.com/problems/number-of-islands/ 문제 파악-2차원 배열이 주어지고, 1이 상하좌우로 있는지 체크하여 섬이 총 몇 개 있는지 센다. (분기체크)m == grid.lengthn == grid[i].length1 grid[i][j] is '0' or '1'.접근 방법-0은 물, 1은 섬. 물 만나거나 범위 벗어나지 않는 이상, 섬 한 덩어리로 본다.-1이면 계속 순회하며 visit 체크(무한 루프 방지)-처음 기준 노드는 ‘1’ 나오면 시작. 타고 가서 상하좌우 dfs 체크⇒ 막히면 return되고, 다른 방향으로 탐색 시작-If 0이거나, 벽이면 순회 끝(base case)코드 구현import java.util.*;class Solution { p..

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/문제 파악-방향을 탐색하는 문제-최소 거리를 구하는 BFS문제n == grid.lengthn == grid[i].length1 grid[i][j] is 0 or 1 접근 방법💡 -좌표 (x,y) -큐에서 poll()하여 방향에 따라 더하거나 뺀다.-8방향은 0,0 기준점을 기준으로 둘러싼 방향-8방향을 2차원 배열로 미리 선언해두어 for문으로 조회하고 현재 값에 더한다.1)시작점 혹은 끝점이 0이 아니거나,2) 끝점까지 가는 명확한 길이 없다면 즉, 큐 순회가 끝날 때까지 끝점에 도달하지 못하고 가는 길이 끊긴다면⇒ -1 리턴 코드 구현class Solution { ..