그래프(tree)
dfs 깊이우선(깊숙이 먼저들어감) - 원하는 결과를 추출해서 뽑아냄
-stack , 재귀함수가 필수이다. 문제는 최대 6까지만 logic 줌.
bfs 너비우선(단계별로)
-탐색조건
-종료조건
package Algorithm;
import java.util.Scanner;
public class DfsExam1 {
static int T;//반복할 수
static int N;//조합하고 싶은 수(Maximum<=6)단계 깊이
static int visited[] = new int[7];//지나간 경로
static int Answer[] = new int[7];
static void dfs(int depth) {
//종료조건
if(depth==N+1) {
for(int i=1;i<=N;i++) {
System.out.print(Answer[i]+" ");
}
System.out.println();
}else {//탐색조건
for(int i=1;i<=N;i++) {
//재귀함수 ->한단계씩 내려간다. 재귀함수리턴 -> 한단계씩 다시 올라감.
if(visited[i]==0) {
visited[i]=1; //같은 값을 접근하면 다시 접근하지 않도록
Answer[depth] = i;
dfs(depth+1);
visited[i]=0; //다시 거쳐서 위로 올라갈수있도록
Answer[depth]=0; //다음 만족하는 값을 다시 배열에 추가할 수 있게
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for(int test_case=1;test_case<=T;test_case++) {
N = sc.nextInt();
for(int i=1;i<=N;i++) {
visited[i]=0;
}
System.out.println("#"+test_case);
dfs(1);
}
}
}
2
3
#1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
4
#2
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
**최소비용문제 -> 전형적인 dfs문제
[외판원 순회 문제]
1번부터 N번까지 번호가 매겨져 있는 도시가 있고, 도시를 사이에 길이 있는 경우에만
이동할 수 있다. 여행을 좋아하는 종민이는 M번 도시에서 출발하여 출발지를
제외한 모든 도시를 정확히 한 번씩만 방문한 후 처음 출발지인 M번 도시로
돌아오려 한다. 이때 도시들 사이의 길을 지날갈 때 지불해야 하는 통행료가 있어,
종민이는 최소한의 비용으로 모든 도시를 여행하고 싶다. 종민이가 모든 도시를
여행할 때 필요한 최소비용을 출력하는 프로그램을 작성하시오.
[입력]
첫 번째 줄에 테스트케이스의 수 T(1<= T <= 10)가 주어진다.
각 테스트케이스 마다 첫 번째 줄에는 도시의 수 N과 출발지 M이 공백을 두고 주어진다.
(3<=N<=10, 1<=M<=N) 다음 N개의 줄에는 각 줄에 N개의 숫자들이 공백을
두고 주어지는데 i번째 줄의 j번째 숫자는 i번째 도시에서 j번째 도시로 가는 드는
통행료 MAT[i][j]를 의미한다. 만약 통행료가 0인 경우는 i도시에서 j도시로 가는 길이
없음을 의미하다. (0<=MAT[i][j]<=50)
[제한조건]
- 도시를 잇는 도로는 일방통행이다. 심지어 i번째 도시에서 j번째 도시로 가는
길은 있어도, j번째 도시에서 i번째 도시로 가는 길은 없을 수도 있다.
- 모든 도시를 정확히 한 번씩만 지나야 함에 유의하라.
[출력]
각 줄마다 "#T(T는 테스트케이스 번호)를 출력한 뒤, 종민이가 M번 도시부터
시작하여 모든 도시를 정확히 한 번씩 순회하고 오는데 드는 통행료 최소값을
출력하시오. 단 불가능할 경우 -1을 출력한다.
[sample]
3
3 1
0 1 1
1 0 10
2 20 0
4 3
0 8 13 30
5 0 6 20
6 11 0 21
7 7 6 0
5 5
0 17 0 3 0
1 0 3 4 5
0 5 0 2 5
44 10 0 0 0
9 3 9 7 0
[sampe output]
#1 13
#2 40
#3 30
*그래프는 인접한 노드
package Algorithm;
import java.util.Scanner;
public class DfsExam2 {
static int T;//반복할 수
static int N,M; //게임을 2,3번 할것이기 때문에 static선언 ,도시 수 & 출발도시
static int Answer;
static int MAT[][] = new int[11][11];
static int visited[] = new int[11];//게임할때마다 리셋해줘야 함.
public static void dfs(int idx, int cost, int cnt) {//위치,비용,방문도시의 수
//종료조건 = 모든 도시를 방문했을 때, 시작점으로 돌아갈 길이 있는 경우
if(cnt == N) {
if(MAT[idx][M] !=0) { //처음으로 다시 돌아가는 길
//기존 답보다 새로운 비용이 더 적은 경우를 찾기
if(Answer ==-1 || Answer > cost +MAT[idx][M]) {
Answer = cost + MAT[idx][M]; //cost가 더 작기때문에
}
}
}else {//탐색조건 = 방문한 적이 없고, 길이 있는 도시만 검색
for(int i=1;i<=N;i++) {
if(visited[i]==0 && MAT[idx][i] !=0) {
//가지치기를 잘해야함.(기존 정답보다 누적비용이 작은 경우 => 탐색 필요)
if(Answer ==-1 || Answer > cost + MAT[idx][i]) {//answer가 더 크다. 재귀함수로 더 돌려야 하는 가치가 있다.
visited[i]=1;
dfs(i, cost+MAT[idx][i], cnt+1);
visited[i] = 0;
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for(int test_case=1;test_case<=T;test_case++) {
N = sc.nextInt();//도시 수
M = sc.nextInt();//출발 도시
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {//비용초기화
MAT[i][j] =0;
}
}
for(int i=1;i<=N;i++) {//값 초기화
visited[i]=0;
}
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
MAT[i][j] = sc.nextInt();//값 입력받음
}
}
visited[M] = 1;
Answer = -1;
//DFS 탐색(위치, 비용, 현재까지 방문한 도시의 수)
dfs(M, 0,1);
System.out.println("#"+test_case + " "+Answer);
}
}
}
화산폭발
세로와 가로의 크기가 N인 정사각형 모양의 격자로 이루어진 섬에 화산이 폭발하였다.
최초 격자의 상태는 초원, 바리케이트, 화산 세 가지 상태로 이루어져 있다.
용암은 화산에서 출발하여 상하좌우 네 방향 중 초원이 있는 곳들을 파괴된 초원으로
바꾸며 펴져나간다.
만약네 방향 중 바리케이트가 설치되어 있거나 혹은 화산이 존재한다면 해당 영역을
지나 갈 수 없다.
또한 격자를 벗어나는 것도 허용되지 않는다.
시간이 충분히 지나 용암이 퍼져나갈 수 있는 모든 영역으로 퍼져나갔을 때,
파괴되지 않은 초원의 최대 크기를 구하는 프로그램을 작성하시오.
<입력>
첫 번째 줄에 테스트케이스의 수 T(1<=T<=10)가 주어진다.
각 테스트케이스마다 첫 번째 줄에는 가로와 세로의 크기 N이 공백을 두고 주어진다.
(3<=N<=100)
다음 N개의 줄에는 각 줄에 N개의 숫자들이 공백을 두고 주어지는데 i번째 줄의
j번째 숫자는 i행 j열의 상태 MAT[i][j]를 나타낸다. MAT[i][j] 값이 0인 경우에는
초원이며, 1인 경우에는 이미 세워진 바리케이트, 2인 경우에는 화산이 폭발한 지점이다.
<출력>
각 줄마다 #T(T는 테스트케이스 번호)를 출력한 뒤, 공백을 두고 용암이 퍼져나가도
파괴되지 않는 초원의 개수를 출력한다.
<sample input]
2
3
0 1 1
0 2 0
1 1 0
4
0 0 0 0
0 2 1 0
0 1 2 1
0 0 1 0
[sampe output]
#1 0
#2 1
자율주행의 최고 Lv4 = 구글
테슬라 양아취 lv2 = 사고나면 자기들이 책임안짐
logic으로 구해야하지. 내가 i,j다 구하는것은 불가능
다음주 월,화는 <자바 팀끼리 실기시험> 필기시험은 안봄
phoneinfo, reservehotel같은 것
package Kosta.Algorithm;
import java.util.ArrayList;
import java.util.Scanner;
public class DfsExam3 {
static int T, N;
static ArrayList<int[]> S = new ArrayList<int[]>();//화산위치 저장
//-1:파괴된 초원, 0:초원, 1:바리케이트, 2:화산
static int MAT[][] = new int[101][101];//지도값 저장
//상하좌우 탐색
static int dr[] = {0, 1, 0, -1};
static int dc[] = {1, 0, -1, 0}; //동북서남
static int Answer;
public static void dfs(int now_row, int now_col) {
//탐색조건
for(int i=0;i<4;i++) {
int nxt_row = now_row + dr[i];
int nxt_col = now_col + dc[i];
//다음 지점이 격자 안에 있는 경우
if(nxt_row >=1 && nxt_row <= N && nxt_col >=1 && nxt_col <= N) {
if(MAT[nxt_row][nxt_col] == 0) {
MAT[nxt_row][nxt_col] = -1;
Answer--;
dfs(nxt_row, nxt_col);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for(int test_case=1;test_case<=T;test_case++) {
N = sc.nextInt();
//지도 초기화
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
MAT[i][j] = 0;
}
}
S.clear();
Answer = 0;
//지도 입력 받기
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
MAT[i][j] = sc.nextInt();
//초원인 경우
if(MAT[i][j] == 0) {
Answer++;
}else if(MAT[i][j] == 2) {
S.add(new int[] {i, j});
}//end else
}//inner for
}//outer for
for(int i=0;i<S.size();i++) {
dfs(S.get(i)[0], S.get(i)[1]);
}
System.out.println("#" + test_case + " " + Answer);
}
}
}
*객체화
Customer(Class) -> CustomerManagement
-name -> List<Customer> c = ArrayList<Customer>
-address
-phoneNo
ArrayList<int[]> S = new ArrayList<int[]>();
객체화할게 없어서 지네릭스타입을 int[]로 가져옴
'FULLSTACK > JAVA' 카테고리의 다른 글
| JAVA PROJECT (0) | 2020.11.13 |
|---|---|
| JAVA 19차시 - (프로젝트)호텔예약시스템 발표, 알고리즘(stack,queue), Tree (0) | 2020.11.13 |
| JAVA 18차시 - Test , 호텔예약프로그램 (프로젝트) (0) | 2020.11.13 |
| JAVA 17차시 - 네트워크 통신 프로그래밍 (0) | 2020.11.13 |
| JAVA 16차시 - File, Thread (0) | 2020.11.12 |