문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이현재 단어(시작 단어: begin)를 words들과 하나씩 비교하면서다른 문자가 1개일 경우, 해당 단어로 갈아타고 카운트를 +1 증가함이를 코드로 표현하면 dfs(next, cnt+1) 이렇게 재귀 호출을 하면서target과 같아졌다면 ans(초기값 INF)와 cnt 중 최솟값을 ans에 저장코드class Solution { static boolean[] v; static String t; static int min = 1
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이해당 문제는 bfs에서 연결 요소의 개수를 찾는 문제이다. 노드를 순회하면서 방문하지 않은 노드가 있다면bfs탐색과 방문처리를 해주고 연결요소의 개수를 1 증가시킨다.(bfs탐색 중에 방문하는 노드에 대해서 방문처리도 해주어야 한다.) 순회가 끝나면 연결 요소의 개수 획득!코드import java.util.*;class Solution { static int n; static int[][] arr; static boolean[] v; public int solution(int N, i..
BFS개념 및 목적- 너비 우선 탐색 알고리즘으로 현재 노드로부터 거리 별 탐색을 하기 위해서 사용- 최단 거리를 구하기 위해(DFS로도 찾을 수는 있지만, 최단 거리를 탐색하는데에는 BFS가 더 효율적)특징- 큐를 사용(현재 노드로 부터 갈 수 있는 그 다음 노드를 탐색하기 위해)- 방문배열 사용(방문처리를 통해 해당 노드에 중복 방문을 방지하기 위해)문제 유형 및 해결 방법1. 연결된 노드(집합 내 노드)의 개수를 구하는 문제큐에서 꺼낼 때마다 카운트를 해준다. 2. 연결 요소의 개수(집합의 개수)를 구하는 문제모든 노드를 방문하면서 방문하지 않은 노드라면 카운트 및 bfs탐색 3. 최단거리 구하는 문제1) int[] / Node를 이용해 다음으로 갈 위치와 가중치(depth, time, ...)를 ..
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이2차원 배열 내 0,0 에서 N-1,M-1 까지 도달하는데 걸리는 최단시간 찾는 문제입니다.최단거리를 구하는 방법은 총 3가지가 있으며, 3가지 방법 모두 구현해보았습니다. (아래의 링크에 최단거리를 구하는 방법에 대해 간단히 적어놓았습니다.) BFS와 다익스트라BFS개념 및 목적- 너비 우선 탐색 알고리즘으로 현재 노드로부터 거리 별 탐색을 하기 위해서 사용- 최단 거리를 구하기 위해(DFS로도 찾을 수는 있지만, 최단 거리를 탐색하는데에는 BFS가 더 효율girinkim.tistory.com 코드1...
문제https://www.acmicpc.net/problem/1753풀이한 정점에서 다른 모든 정점까지의 최단거리를 구하는 다익스트라 알고리즘으로 해결 가능한 문제 입력받은 간선으로 list 배열을 통해 정점 간 간선을 이어주고(해당 문제에서는 단방향)정점 별 최단거리를 기록 할 dist 배열을 INF로 초기화를 해준다. 그 다음 시작 정점(S)을 기준으로 다익스트라 알고리즘을 진행한다. 0. 초기 셋팅시작 정점을 기준으로, dist[S] = 0로 초기화최소 힙을 위해 우선순위 큐를 사용하여 가중치를 기준으로 오름차순 정렬pq에 정점 추가 1. 다익스트라dist[다음 노드] > dist[현재 노드] + 다음 노드로 가기 위해 발생하는 가중치 라면dist[다음 노드] = dist[현재 노드] + 다음 노드..
문제https://www.acmicpc.net/problem/2178풀이2차원 배열 내 0,0 지점에서 N-1,M-1까지 도달하는데 걸리는 최단시간을 구하는 문제입력 값을 바탕으로 2차원 배열을 형성하고 1) 큐 사이즈 순회 및 time 카운팅 방법2) 큐에 다음 위치와 현재까지 걸린 시간을 넘겨주는 방법 두 가지 방법 중 하나를 선택해 해결하면 된다.이러한 방식에 대한 설명은 아래 링크를 참고하면 된다. 2차원 배열 내에서 최단시간 탐색 방법 - [백준] 숨바꼭질 [백준] 1697. 숨바꼭질(Java)문제https://www.acmicpc.net/problem/1697풀이bfs 탐색을 진행하면서 K에 도달하기까지 걸리는 최소시간을 구하는 문제2가지 방법이 존재함 1) qSize만큼 순회하면서 time ..
문제https://www.acmicpc.net/problem/1697풀이bfs 탐색을 진행하면서 K에 도달하기까지 걸리는 최소시간을 구하는 문제2가지 방법이 존재함 1) qSize만큼 순회하면서 time 체크하는 방법현재 큐 사이즈만큼만 순회하면서현재위치 -1, 현재위치 + 1, 현재위치 * 2에 해당하는 값들이범위를 넘는지(0 방문처리 및 큐에 다음 위치 값만 넘겨줌큐 사이즈만큼 순회를 마쳤다면 time ++ 이렇게 순회하면서현재위치가 K라면 time 출력 및 종료2) 큐에 다음 위치와 현재까지 걸린 시간을 넘겨주는 방법node/int[]를 사용해서 큐에 다음 위치 값과 현재까지 걸린 시간을 넘겨주는 방법1번과 동일하게 다음으로 갈 위치에 대해, 유효범위인지 방문했는지 확인하고방문처리 및 큐에 다음으로..
문제https://www.acmicpc.net/problem/4485풀이0,0 → N-1, N-1까지 이동하는데 드는 최소 비용을 구하는 문제 포인트는전역으로 2차원 int 방문배열을 두고, bfs를 돌면서다음으로 갈 곳의 비용이 현재 위치까지 오는데 드는 비용 + 현재 위치에서 다음 위치로 가는데 드는 비용보다 클 경우다음으로 갈 곳의 비용 = 현재 위치까지 오는데 드는 비용 + 현재 위치에서 다음 위치로 가는데 드는 비용으로 갱신해주면 된다.코드import java.io.*;import java.util.*;class Main { static int N; static int[][] arr, v; static int[] dr = {-1, 0, 1, 0}; static int[] d..
