dfs

📖 문제 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 💡 풀이 방식 • 백트래킹 + DFS (0,0)부터 dfs를 한다. 해당 점의 인접한 4방향 탐색을 통해 격자 범위 내에 있고, 지금까지 나온 적 없는 알파벳인 경우 마저 탐색을 진행하며 최대 경로를 찾는다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 ..

📖 문제 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 💡 풀이 방식 • BFS 1. 격자의 모든 칸을 입력받는다. 2. 격자의 모든 점을 돌면서, 방문한 적 없는 글자(1)인 부분에서 BFS를 수행하고, 그 수행 횟수를 구한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 import java.util.*; import j..

📖 문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 💡 풀이 방식 • BFS w와 h가 0이 아닐 때만 아래와 같이 진행한다. 1. 격자의 값을 입력받는다.2. 모든 점을 탐색하며 방문하지 않은 땅에 대해 BFS 탐색을 실행하고, 섬 개수를 증가시킨다. - BFS 탐색: 격자 범위를 벗어나지 않고, 방문한 적 없고, 땅(1)인 값에 대해 8방향 탐색 수행 (상하좌우 + 대각선 4방향) 3. 구한 섬 개수를 출력한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS 필요 자료구조 - 속성 선택 여부 나타내는 배열 bolean[] visited = new boolean[relation[0].length] - 후보키 목록 List list 1. 1부터 N개의 속성을 모두 선택하며 후보키가 가능한지(= 값이 중복되는 게 없는지) 확인한다. (DFS) : 조합이 만들어지면, 유일성 검사와 최소성 검사한 후, 조합을 추가한다. 1-1) 선택된 속성으로 후보키를 생성한다. List tmpList = new ArrayList();// 임시 후보키 목..

📖 문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 풀이 방식 • DFS + BFS + 브루트포스 1. 입력을 받으면서 빈 칸의 위치와 바이러스의 위치를 리스트에 저장해둔다. - 빈 칸 위치 저장한 이유 : 빈 칸 위치들 중 3개만 뽑으려고 할 때 완전탐색으로 모든 빈 칸 위치 안 찾으려고 - 바이러스 위치 저장한 이유 : 완전탐색으로 바이러스 위치 안 찾으려고 2. 빈 칸 중 3개를 뽑아 벽을 세우고, 바이러스를 퍼뜨린다. 2-1) 빈 칸 중 3개 뽑는 방법 : DFS private static void dfs(..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS 필요 자료구조 - 그룹 별 상자 갯수 저장할 int형 우선순위 큐 (상자 갯수가 많은 순으로 내림차순 정렬) - 상자가 열림/닫힘을 표현할 boolean형 방문 표시 배열 1. cards 배열의 0부터 cards.length-1번째 원소까지 돌며 방문하지 않은 칸이 있다면, 방문 처리하고 그룹 내에 포함된 상자 수를 세러 간다. (dfs 메소드) 2. DFS 메소드 구현 - 종료 조건 : 열었던 상자인 경우(visited[idx] == true), 여태껏 구한 상자 갯수를 큐..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS / BFS + 그리디 필요 자료구조 - 인접 정점 정보 저장할 ArrayList 배열 - 정점 방문 표시할 boolean형 배열 - 가중치 정보 저장할 long형 배열 1. 배열 a의 전체 합한 값이 0인지 확인한다. 0이 아니라면 -1을 리턴한다. 2. 인접 정보를 저장할 ArrayList 배열을 생성해 인접한 값들 정보를 저장한다. 3. 방문 표시 배열과 DFS를 통해 leaf 노드까지 쭉 탐색했다가 차례대로 올라온다. (탐색 방향 : 위에서 아래) 4. 부모 정점은 자식..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 재귀 (분할정복) 1. (0,0) 좌표에서부터 재귀를 시작한다. 2. 만약 해당 좌표에서 범위까지 있는 모든 수들이 같다면 압축이 가능하므로 압축하고, 0/1의 갯수에 +1한다. 압축이 불가능하다면, 4분할 재귀를 시작한다. divide(x, y, size/2); divide(x, y + size/2, size/2); divide(x + size/2, y, size/2); divide(x + size/2, y + size/2, size/2); 🔺 코드 1 2 3 4 5 6 7 8 9..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• BFS / DFS1. 응시자가 있는 자리 P에서 BFS를 수행한다.- 해당 응시자 위치에서 4방향 탐색 시 격자 범위를 벗어나고, 출발점 P인 경우 탐색하지 않는다.if(!inRange(nx, ny) || (nx == x && ny == y)) continue; - 맨해튼 거리 2 이하인 곳에 또 다른 응시자P가 존재한다면, 거리두기 실패- 맨해튼 거리가 2 미만이고, 빈 테이블이 존재하는 경우, 큐에 다음 탐색 위치를 추가해 마저 탐색한다.if(s[nx].charAt(n..