BFS
백준 벽 부수고 지나가기
미로의 최단거리 통로
import java.util.*;
class Point{
public int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
}
class Main {
public int solution(int[][] board){
Queue<Point> Q=new LinkedList<>();
int[][] dist = new int[7][7];
int[] dx= {-1,0,1,0};
int[] dy= {0,1,0,-1};
Q.offer(new Point(0, 0));
board[0][0]=1;
while(!Q.isEmpty()) {
Point tmp=Q.poll();
for(int i=0;i<4;i++) {
int nx=tmp.x+dx[i];
int ny=tmp.y+dy[i];
if((nx>=0&&nx<7&&ny>=0&&ny<7) && board[nx][ny]==0) {
board[nx][ny]=1;
Q.offer(new Point(nx, ny));
dist[nx][ny]=dist[tmp.x][tmp.y]+1;
}
}
}
if(dist[6][6]==0) { return -1; }
return dist[6][6];
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int arr[][]= {{0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 0}, {0, 0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 0, 1, 1}, {1, 1, 0, 1, 0, 0, 0}, {1, 0, 0, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 0, 0}};
System.out.println(T.solution(arr));
}
}그래프
- 무방향 그래프
- 방향 그래프
- 가중치 방향그래프
경로 탐색(인접행렬)
1번 정점에서 n번 정점으로 가는 모든 경로의 수 구하기
import java.util.*;
class Main {
int[] check;
int[][] graph;
int target,answer=0;
public void DFS(int v) {
if(v==target) answer++;
else {
for(int i=0;i<=target;i++) {
if(graph[v][i]==1 && check[i]==0) {
check[i]=1;
DFS(i);
check[i]=0;
}
}
}
}
public int solution(int n, int[][] edge){
graph = new int[n+1][n+1];
check = new int[n+1];
target=n;
for(int[] x:edge) {
graph[x[0]][x[1]]=1;
}
check[1]=1;
DFS(1);
return answer;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int arr[][]= {{1,2}, {1, 3}, {1, 4},
{2, 1}, {2, 3}, {2, 5}, {3, 4}, {4, 2}, {4, 5}};
System.out.println(T.solution(5,arr));
}
}경로 탐색(인접리스트)
인접리스트 사용하자!!
import java.util.*;
class Main {
int target,answer=0;
ArrayList<ArrayList<Integer>> graph;
int[] check;
public void DFS(int v) {
if(v==target) answer++;
else {
for(int nv:graph.get(v)) {
// v번째 객체에는 연결되어있는 노드만 추가되어있음
if(check[nv]==0) { // 무조건 연결되어있으므로 방문 여부만 체크
check[nv]=1;
DFS(nv);
check[nv]=0;
}
}
}
}
public int solution(int n, int[][] edge){
// 그래프 공간 만들기
graph = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<=n;i++) {
graph.add(new ArrayList<Integer>());
}
check = new int[n+1];
target=n;
// 그래프에 값 추가
for(int[] x:edge) {
graph.get(x[0]).add(x[1]);
}
check[1]=1;
DFS(1);
return answer;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int arr[][]= {{1,2}, {1, 3}, {1, 4},
{2, 1}, {2, 3}, {2, 5}, {3, 4}, {4, 2}, {4, 5}};
System.out.println(T.solution(5,arr));
}
}동아리 개수
import java.util.*;
class Point{
public int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
}
class Main {
int target,answer=0;
ArrayList<ArrayList<Integer>> graph;
int[] check;
public void DFS(int v) {
for(int nv:graph.get(v)) {
if(check[nv]==0) {
check[nv]=1;
DFS(nv);
}
}
}
public int solution(int n, int[][] edge){
// 그래프 공간 만들기
graph = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<=n;i++) {
graph.add(new ArrayList<Integer>());
}
check = new int[n+1];
// 그래프에 값 추가
for(int[] x:edge) {
graph.get(x[0]).add(x[1]);
graph.get(x[1]).add(x[0]);
}
for(int i=0;i<n;i++) {
if(check[i]==0) {
check[i]=1;
DFS(i);
answer++;
}
}
return answer;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int arr[][]= {{1,2}, {2, 3}, {1, 4}, {1, 5}};
System.out.println(T.solution(7,arr));
}
}DFS
섬나라 아일랜드
섬 개수 구하기
import java.util.*;
class Main {
int answer=0;
int[] dx= {-1,-1,0,1,1,1,0,-1};
int[] dy= {0,1,1,1,0,-1,-1,-1};
public void DFS(int x, int y, int[][] board) {
for(int i=0;i<8;i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0&&nx<board.length&&ny>=0&&ny<board.length && board[nx][ny]==1) {
board[nx][ny]=0;
DFS(nx, ny, board);
}
}
}
public int solution(int[][] board){
int n=board.length;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(board[i][j]==1) { // 섬 하나 찾기 시작
board[i][j]=0;
DFS(i,j,board);
answer++; // 섬 하나 찾기 완료
}
}
}
return answer;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int arr[][]= {{1, 1, 0, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 1, 1}, {1, 1, 0, 1, 1, 0, 0},
{1, 0, 0, 0, 1, 0, 0}, {1, 0, 1, 0, 1, 0, 0}};
System.out.println(T.solution(arr));
}
}줄다리기 (순열)
Stack<Integer> stack = new Stack<>();
int answer=0;
int[][] relation;
int[] visit;
public void DFS(int v) {
if(v==7) {
boolean flag=true;
int cnt=0, a=0, b=0;
for(int x:stack) {
if(cnt==0) {
a=x;
cnt++;
}
else {
b=x;
if(relation[a][b]==1) {
flag=false;
break;
}
a=b;
}
}
if(flag) answer++;
}
else {
for(int i=1;i<8;i++) {
if(visit[i]==0) {
stack.push(i);
visit[i]=1;
DFS(v+1);
stack.pop();
visit[i]=0;
}
}
}
}import java.util.*;
class Main {
Stack<Integer> stack = new Stack<>();
int answer=0;
int[][] relation;
int[] visit;
public void DFS(int v) {
if(v==7) {
answer++;
}
else {
for(int i=1;i<8;i++) {
// 싸움이 일어나는 경우엔 순열 구하지 않고 지나감
if(!stack.isEmpty() && (relation[stack.peek()][i]==1)) { continue; }
if(visit[i]==0) {
stack.push(i);
visit[i]=1;
DFS(v+1);
stack.pop();
visit[i]=0;
}
}
}
}
public int solution(int[][] fight){
relation=new int[8][8];
for(int[] x:fight) {
relation[x[0]][x[1]]=1;
relation[x[1]][x[0]]=1;
}
visit=new int[8];
DFS(0);
return answer;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int arr[][]= {{1,3},{5,7},{4,2}};
System.out.println(T.solution(arr));
}
}바둑대회 (조합)
ch로 체크해가면서 DFS
v=n/2까지 되면 체크 된거는 A, 체크 안된거는 B에 인덱스 번호 넣고
이걸 보고 cans에서 찾아서 능력치 계산
import java.util.*;
class Main {
Stack<Integer> stack = new Stack<>();
int answer=2147000000, n=6;
int[] ch;
public void DFS(int L, int s, int[][] cans) {
if(L==n/2) {
ArrayList<Integer> A=new ArrayList<>();
ArrayList<Integer> B=new ArrayList<>();
for(int i=0;i<n;i++) {
if(ch[i]==1) A.add(i);
else B.add(i);
}
int Asum=0,Bsum=0;
for(int i=0;i<L;i++) { // L이 아니라 A.size()로 해도 됨
Asum+=cans[A.get(i)][0];
Bsum+=cans[B.get(i)][1];
}
answer=Math.min(answer, Math.abs(Asum-Bsum));
}
else { // 조합 구하는 코드 그대로 가져옴
for(int i=s;i<n;i++) {
ch[i]=1;
DFS(L+1, i+1, cans);
ch[i]=0;
}
}
}
public int solution(int[][] cans){
n=cans.length;
ch=new int[n];
DFS(0,0,cans);
return answer;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int arr[][]= {{87,84},{66,78},{94,94},{93,87},{72,92},{78,63}};
System.out.println(T.solution(arr));
}
}BFS
타일 점프
최소 점프 횟수 구하기
import java.util.*;
class Main {
int answer=0;
int[] check;
public int solution(int[] nums){
Queue<Integer> Q = new LinkedList<>();
int n=nums.length;
check=new int[n];
Q.offer(0);
check[0]=1;
int level=0;
while(!Q.isEmpty()) {
int len=Q.size();
for(int i=0;i<len;i++) {
int x=Q.poll();
for(int j=1;j<=nums[x];j++) {
int nx=x+j;
if(nx==n-1) {
return level+1;
}
if(nx<n && check[nx]==0) {
Q.offer(nx);
check[nx]=1;
}
}
}
level++;
}
return -1;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int arr[]= {2, 2, 0, 2, 1, 1};
int arr1[]= {1, 0, 1, 1, 3, 1, 2, 1};
System.out.println(T.solution(arr));
System.out.println(T.solution(arr1));
}
}
노력형 인간