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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
package baekjoon;
 
import java.util.*;
import java.io.*;
 
//이게 왜 bfs로 풀이 하는 건지 잘 모르겠다.
public class baekjoon9019{
 
    static int n;
    static int D;
    static int S;
    static int L;
    static int R;
 
public static void main(String[] args)throws IOException{
 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
 
    for(int i=0;i<T;i++){
    StringTokenizer st = new StringTokenizer(br.readLine()," ");
    int A = Integer.parseInt(st.nextToken());
    int B = Integer.parseInt(st.nextToken());
 
    DSLR dslr = new DSLR(A,B);
    System.out.println(dslr.getCommands());
    }
    br.close();
}
 
    static class DSLR{
        private int A,B;
        private boolean[] visited;
        
        public DSLR(int a,int b){
            A = a;
            B = b;
            visited = new boolean[10001];  
        }
 
        public String getCommands(){
 
            //큐를 설정할떄 이렇게 설정하는거 이해 안간다.
            Queue<Register> registers = new LinkedList<>();
             registers.offer(new Register(A,""));
             visited[A] = true;
             while(!registers.isEmpty()){
                 Register register = registers.poll();
                 if(register.getNum() == B){
                     return register.getCommand();
                 }
 
                 if(!visited[commandD(register.getNum())]){
                     int num = commandD(register.getNum());
                     visited[num] = true;
                     StringBuilder commands = new StringBuilder(register.getCommand());
                     registers.offer(new Register(num, commands.append("D").toString()));
                 }
                 if(!visited[commandS(register.getNum())]){
                     int num = commandS(register.getNum());
                     visited[num] = true;
                     StringBuilder commands = new StringBuilder(register.getCommand());
                    registers.offer(new Register(num, commands.append("S").toString()));
                
                }
 
                if(!visited[commandL(register.getNum())]){
                    int num = commandL(register.getNum());
                    visited[num] = true;
                    StringBuilder commands = new StringBuilder(register.getCommand());
                    registers.offer(new Register(num, commands.append("L").toString()));
                }
                
                if(!visited[commandR(register.getNum())]){
                    int num = commandR(register.getNum());
                    visited[num] = true;
                    StringBuilder commands = new StringBuilder(register.getCommand());
                    registers.offer(new Register(num, commands.append("R").toString()));
 
                }
             }
             return null;
            }
 
    private int commandD(int n){ //2배
        return (n*2) % 10000;
    }
    private int commandS(int n){ //n-1
        return (n == 0) ? 9999 : n-1;
    }
    private int commandL(int n){ //왼쪽 시프트
 
        //n이 1234라면 1234%1000 = 234 이고 234*10 = 2340이고 (1234/1000) = 1이니까 여기서 1더하면 2341이된다.
        return (n%1000) * 10 + (n/1000);
    }
    private int commandR(int n){ //오른쪽 시프트
 
        //n이 1234라면 1234%10 = 4이고 4에서 *1000을 하면 4000이 나오고 4000 + (1234/10) = 4123 이나온다. 
        return (n%10) * 1000 + (n/10);
    }
    
 
    //등록할 Register클래스를 만들어주고
    class Register{
        private int num; //숫자와
        private String command; //명령어값을 초기화 한다.
 
        //생성자를 만들고
        public Register(int num, String command){
            this.num = num;
            this.command = command;
        }
 
        //** 이부분 이해 안감 */
        //숫자를 받아온다.
        public int getNum(){
            return num;
        }
        //명령어 값을 받아온다.
        public String getCommand(){
            return command;
            }
        }
    }
}
 
/*
    int number[] = new int[10001];
    //D는 두배
    D = n*2;
    System.out.print(D);
    //S 는 n-1
    S = n-1;
    System.out.print(S);
    //L은 왼쪽 시프트
    L = n<<10;
    System.out.print(L);
    //R은 오른쪽 시프트
    R = n>>10;
    System.out.print(R);
    }
}
*/
cs


저작자표시

'BFS,DFS_문제풀이' 카테고리의 다른 글

백준 2668 > 숫자고르기 > DFS 기본중에 기본인 문제  (0) 2019.02.26
백준 1325 > 효율적인 해킹 > DFS기본문제 (시간초과나는 이유 알아내기)c++로 푸는게 가장 깔끔할 수도 있따.  (1) 2019.02.26
백준 2178 > 미로탐색 > bfs의 기본중의 기본 문제 꼭 이거 먼저 보고 시작하기 (String word = sc.nextLine(); Stirng array[] = word.split(" "); , nextY,nextY,split,visited,Integer,parseInt,LinkedList,charAt,Queue,Dot )  (0) 2019.02.26
백준 16940 > BFS스페셜 저지 > 트리에서 BFS 방문순서 올바른지 확인하기 (bfs)  (0) 2019.02.25
백준 2606 > 바이러스 > 자바 bfs기초문제2(BufferdReader,InputStreamReader,LinkedList,Queue,visit,Integer.parseInt,trm,split)  (0) 2019.02.24

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
//DFS기본중에 기본인 문제
 
package baekjoon;
import java.util.*;
import java.io.*;
public class baekjoon2668{
 
    static int[] arr;
    static boolean[] visited;
    //last는 마지막 점이 출발점과 같다면 사이클이 완성 됬으므로 리스트에 추가 이게 -> dfs하려면 사이클 해야되는구나 estsoft문제 2번 문제와 유사
    static int last;
    //ArrayList로 하나 변수를 두어야 하고
    static ArrayList<Integer> list;
 
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        arr= new int[N+1];
        visited = new boolean[N+1];
        list = new ArrayList<Integer>();
        for(int i=1;i<=N;i++){
            arr[i] = sc.nextInt();
        }
        for(int i=1;i<=N;i++){
            visited[i] = true; //무한 재귀에 빠지면 안되므로 첫 시작점도 방문으로 체크
            last = i;
            DFS(i);
            visited[i] = false; //다음 숫자를 dfs해야 하니까 초기화 시켜준다.
        }
        Collections.sort(list);//작은 수 부터 출력해야 하니까 정렬
        System.out.println(list.size());
        for(int i : list){
            System.out.println(i); //list들을 하나씩 출력해준다.
        }
    }
    public static void DFS(int i){
        if(!visited[arr[i]]){ //이전에 방문한 점이 아니여야 한다.
            visited[arr[i]] = true; //방문했으므로 true;
            DFS(arr[i]);
            visited[arr[i]] = false; //다음 DFS를 위하여 false
        }
        if(arr[i] == last){ //마지막 점이 출발점과 같다면 사이클이 완성됬으므로 리스트에 추가
            list.add(last);
        }
    }
}
cs


저작자표시

'BFS,DFS_문제풀이' 카테고리의 다른 글

백준 9019 > DSLR > BFS로 풀어야 한다는거가 이해 안가고, Queue부분 코딩하는거 이해 안감  (0) 2019.02.28
백준 1325 > 효율적인 해킹 > DFS기본문제 (시간초과나는 이유 알아내기)c++로 푸는게 가장 깔끔할 수도 있따.  (1) 2019.02.26
백준 2178 > 미로탐색 > bfs의 기본중의 기본 문제 꼭 이거 먼저 보고 시작하기 (String word = sc.nextLine(); Stirng array[] = word.split(" "); , nextY,nextY,split,visited,Integer,parseInt,LinkedList,charAt,Queue,Dot )  (0) 2019.02.26
백준 16940 > BFS스페셜 저지 > 트리에서 BFS 방문순서 올바른지 확인하기 (bfs)  (0) 2019.02.25
백준 2606 > 바이러스 > 자바 bfs기초문제2(BufferdReader,InputStreamReader,LinkedList,Queue,visit,Integer.parseInt,trm,split)  (0) 2019.02.24
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package baekjoon;
import java.util.*;
import java.io.*;
import java.util.StringTokenizer;
 
//컴퓨터가 아래 M = 4개의 줄에 신뢰하는 관계를 설명한다.
//1번부터 N = 5번까지 숫자를 가질 수 있다.
//dfs문제라고 하였다.
//3이 1을 신뢰하고 -> 1을 해킹하면 3을 해킹
//3이 2를 신뢰하고 -> 2를 해킹하면 3을 해킹
//4가 3을 신뢰하고 -> 3을 해킹하면 4을 해킹 -> 1,2를 해킹
///5가 3을 신뢰한다. ->3을 해킹하면 5을 해킹 ->1,2,4를 해킹
//따라서 최대 해킹할 수 있는 컴퓨터 번호가 1,2
//dfs활용하고 StringBuilder활용해 보자
/*
public class baekjoon1325{
    //static int arr[][];
    //static boolean visit[][];
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,-1,1};
    static int N;
    static int M;
    //ArrayList를 구해줄 a 배열
    static ArrayList<Integer>[]  a = (ArrayList<Integer>[]) new ArrayList[10001];
    
    public static void main(String[] args)throws IOException{
        //신뢰 하는 관계와 신뢰하지 않는 관계를 어떻게 파악하는거지?
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer st = new StringTokenizer(br.readLine());
        
        //N = Integer.parseInt(st.nextToken());
        //M = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        N = sb.readLine();
        M = sb.readLine();
        for(int i=1;i<=N;i++){
            //위에서 static해준 ArrayList배열a
            a[i] = new ArrayList<Integer>();
        }
        for(int i=0;i<M;i++){
            int v1 = 
        }
        //arr = new int[N][M];
        //visit = new boolean[N][M];
        // ArrayList를 하나 만들어 줘야 한다.
      //  arr[N].add[M];
        /*
        for(int i=0;i<N;i++){
            String a = br.readLine();
            for(int j=0;j<M;j++){
                arr[i][j] = a.charAt(j)-'0';
                visit[i][j] = false;
            }
        }
        visit[0][0] = true;
        bfs(0,0);
        
    }
}
*/
 
public class baekjoon1325{
static ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[10001];
static boolean[] visited = new boolean[10001];
static int[] ans = new int[10001];
static int cnt = 0;
 
public static void main(String[] args)throws IOException {
    //StringBuilder사용하는거랑 Scanner사용하는거 차이점 알아내기
    StringBuilder sb = new StringBuilder();
    Scanner sc =new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
 
    for (int i = 1; i <= n; i++) {
        a[i] = new ArrayList<Integer>();
    }
 
    for (int i = 0; i < m; i++) {
        int v1 = sc.nextInt();
        int v2 = sc.nextInt();
 
        a[v1].add(v2);
    }
 
    int max = 0;
    for (int i = 1; i <= n; i++) {
        visited = new boolean[10001];
        dfs(i);
    }
 
    for (int i = 1; i <= n; i++) {
        if (max < ans[i]) {
            max = ans[i];
        }
    }
 
    for (int i = 1; i <= n; i++) {
        if (max == ans[i]) {
            sb.append(i + " ");
        }
    }
 
    System.out.println(sb.toString());
}
 
public static void dfs(int v) {
    visited[v] = true;
 
    for (int vv : a[v]) {
        if (!visited[vv]) {
            ans[vv]++;
            dfs(vv);
            }
        }
    }
}
cs


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
65
66
67
68
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M;
    static int[] vertex;
    static int[] nodeMap;
    static int[] ans;
    static int result;
    static ArrayList<Integer>[] list = new ArrayList[10001];
 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        result = 0;
        nodeMap = new int[10001];
        ans = new int[10001];
 
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
 
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
 
            list[n1].add(n2);
            nodeMap[n1] = n2;
        }
 
        for (int i = 1; i <= N; i++) {
            vertex = new int[100001];
            dfs(i);
        }
 
        for (int i = 1; i <= N; i++) {
            if (result == ans[i]) {
                System.out.print(i + " ");
            }
        }
 
    }
 
    static void dfs(int node) {
 
        vertex[node] = 1;
 
        for (int i : list[node]) {
 
            if (vertex[i] == 0) {
                ans[i] += 1;
                result = Math.max(result, ans[i]);
                dfs(i);
            }
        }
 
    }
}
cs


저작자표시

'BFS,DFS_문제풀이' 카테고리의 다른 글

백준 9019 > DSLR > BFS로 풀어야 한다는거가 이해 안가고, Queue부분 코딩하는거 이해 안감  (0) 2019.02.28
백준 2668 > 숫자고르기 > DFS 기본중에 기본인 문제  (0) 2019.02.26
백준 2178 > 미로탐색 > bfs의 기본중의 기본 문제 꼭 이거 먼저 보고 시작하기 (String word = sc.nextLine(); Stirng array[] = word.split(" "); , nextY,nextY,split,visited,Integer,parseInt,LinkedList,charAt,Queue,Dot )  (0) 2019.02.26
백준 16940 > BFS스페셜 저지 > 트리에서 BFS 방문순서 올바른지 확인하기 (bfs)  (0) 2019.02.25
백준 2606 > 바이러스 > 자바 bfs기초문제2(BufferdReader,InputStreamReader,LinkedList,Queue,visit,Integer.parseInt,trm,split)  (0) 2019.02.24

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package baekjoon;
//미로탐색
//단순 bfs문제로 어렵지 않다
//1. 다음 방문할 점을 큐에 넣는다.
//2. 큐에서 빼온다음 다음 갈 곳이 조건에 벗어나지 않는다면 큐에 넣는다.
//3. 큐가 빌때까지 계속한다.(내가 원하는 점에 왔을 때 return해줘도 가능하지 않을까?)
import java.util.*;
import java.io.*;
 
 
public class baekjoon2178{
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,-1,0,1};
    static int N;
    static int M;
 
    public static void main(String[] args) throws Exception{
 
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       // BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       Scanner sc = new Scanner(System.in);
 
       // N = br.read();
      //  N = sc.nextInt();
       // M = br.read();
      // M = sc.nextInt();
      //이부분이 중요 자꾸 4 6 입력시 string값 받으면서 동시 입력 안되는데 이런식으로 string을 split 끊어 줘야 한다.
       String word = sc.nextLine();
       String array[] =word.split(" "); 
 
       N = Integer.parseInt(array[0]);
       M = Integer.parseInt(array[1]);
 
        arr = new int[N][M];
        visited = new boolean[N][M];
 
        for(int i=0;i<N;i++){
 
           // String str = String.valueOf(br.readLine());
          // String str = br.readLine();
          String str = sc.nextLine();
            for(int j=0;j<M;j++){
                arr[i][j] = str.charAt(j)-'0';
                visited[i][j] = false;
            } 
        }
        visited[0][0] = true;
        BFS(0,0);
        System.out.println(arr[N-1][M-1]);
 
    }
    static public void BFS(int x,int y){
        Queue<Dot> q = new LinkedList<Dot>();
        q.add(new Dot(x,y));
 
        //큐가 끝날때까지
        while(!q.isEmpty()){
            Dot d = q.poll();
            for(int i=0;i<4;i++){
                //다음 방문할 좌표 nextX, nextY
                int nextX = d.x + dx[i];
                int nextY = d.y + dy[i];
 
                //다음 좌표가 범위를 넘어갈때 건너 뛰기
                if(nextX < 0 || nextY<0 || nextX >= N || nextY >=M){
                    continue;
                }            
                //이미 방문했던 점이면 건너 뛰기
                if(visited[nextX][nextY] || arr[nextX][nextY] == 0){
                    continue;
                }
                //다음에 방문할 좌표를 큐에 넣는다.
                q.add(new Dot(nextX,nextY));
                //배열 안에 다음 방문할 곳은 현재 방문햇던 점보다 1칸 더 가야 하므로 +1
                arr[nextX][nextY] = arr[d.x][d.y] + 1;
                //다음 좌표는 방문했음으로 표시
                visited[nextX][nextY] = true;
            }
        }
    }
}
 
class Dot{
    int x;
    int y;
    Dot(int x,int y){
        this.x =x;
        this.y =y;
    }
}
 
cs

비슷한듯 다르게 푸신분

StringTokenizer를 쓰면 메모리 절약되고 하나씩 끊어서 출력을 할 수 있다.
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
 
public class Main{
    
    static int arr[][];
    static boolean visit[][];
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,-1,1};
    static int r,c;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
        StringTokenizer st =new StringTokenizer(br.readLine());
        
        r =Integer.parseInt(st.nextToken());
        c =Integer.parseInt(st.nextToken());
        
        arr = new int[r][c];
        visit = new boolean[r][c];
        
        for(int i=0; i<r;i++) {
            String a = br.readLine();
            for(int j=0; j<c; j++) {
                arr[i][j] = a.charAt(j)-'0';
                visit[i][j] =false;
            }
        }
        
        visit[0][0] =true;
        bfs(0,0);
        bw.write(String.valueOf(arr[r-1][c-1]));
        bw.flush();
    }
 
 
    private static void bfs(int x, int y) {
        // TODO Auto-generated method stub
        Queue<Node> q = new LinkedList<Node>();
        q.add(new Node(x,y));
        
        while(!q.isEmpty()) {
        Node curNode = q.poll();
        
        for(int i=0; i<4; i++) {
            int nextX = curNode.x+dx[i];
            int nextY = curNode.y+dy[i];
            
            
            if (nextX < 0 || nextY < 0 || nextX >= r || nextY >= c) {
                continue;
            }
           
            if (visit[nextX][nextY] || arr[nextX][nextY] == 0) {
                continue;
            }
            
            q.add(new Node(nextX, nextY));
            
            arr[nextX][nextY] = arr[curNode.x][curNode.y]+1;
            visit[nextX][nextY] = true;
        }
        }
        
        
        
    }
 
 
}
 
class Node{
    int x,y;
    public Node(int x, int y) {
        // TODO Auto-generated constructor stub
        this.x = x;
        this.y = y;
    }
}
[출처] [BOJ]2178번, 미로탐색|작성자 wellcoding
cs


저작자표시

'BFS,DFS_문제풀이' 카테고리의 다른 글

백준 2668 > 숫자고르기 > DFS 기본중에 기본인 문제  (0) 2019.02.26
백준 1325 > 효율적인 해킹 > DFS기본문제 (시간초과나는 이유 알아내기)c++로 푸는게 가장 깔끔할 수도 있따.  (1) 2019.02.26
백준 16940 > BFS스페셜 저지 > 트리에서 BFS 방문순서 올바른지 확인하기 (bfs)  (0) 2019.02.25
백준 2606 > 바이러스 > 자바 bfs기초문제2(BufferdReader,InputStreamReader,LinkedList,Queue,visit,Integer.parseInt,trm,split)  (0) 2019.02.24
백준 2638 >치즈 > 자바 bfs풀이의 기초버전(Pair,LinkedList,map,dx,dy,Queue,loop,visit)  (0) 2019.02.23
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
65
66
package baekjoon;
 
import java.util.*;
import java.io.*;
 
public class baekjoon16940{
    static int n;
    static int m;
    static int map[][];
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,-1,1};
    static boolean[] visit;
    public static void main(String[] args){
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        visit = new boolean[n+1];
        
 
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                map[i][j] = sc.nextInt();
            }
        }
    }
        public static void bfs(){
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0,0));
 
        while(!q.isEmpty()){
            Pair p = q.poll();
 
            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
 
                if(nx<0 || ny<0 || nx>=n || ny>=m)
                    continue;
                
                if(map[nx][ny]==0 && visit[nx][ny]==0){
                    visit[nx][ny]  = 1;
                    q.add(new Pair(nx,ny));
                }
                if(map[nx][ny]==1){
                    visit[nx][ny]++;
                    if(visit[nx][ny]>=2)
                    map[nx][ny]=0;
                }
            }
        }
    }
 
 
 
static class Pair{
    int x,y;
    Pair(int x,int y){
        this.x = x;
        this.y = y;
    }
}
}
cs


저작자표시

'BFS,DFS_문제풀이' 카테고리의 다른 글

백준 1325 > 효율적인 해킹 > DFS기본문제 (시간초과나는 이유 알아내기)c++로 푸는게 가장 깔끔할 수도 있따.  (1) 2019.02.26
백준 2178 > 미로탐색 > bfs의 기본중의 기본 문제 꼭 이거 먼저 보고 시작하기 (String word = sc.nextLine(); Stirng array[] = word.split(" "); , nextY,nextY,split,visited,Integer,parseInt,LinkedList,charAt,Queue,Dot )  (0) 2019.02.26
백준 2606 > 바이러스 > 자바 bfs기초문제2(BufferdReader,InputStreamReader,LinkedList,Queue,visit,Integer.parseInt,trm,split)  (0) 2019.02.24
백준 2638 >치즈 > 자바 bfs풀이의 기초버전(Pair,LinkedList,map,dx,dy,Queue,loop,visit)  (0) 2019.02.23
DFS(C++) 나동빈님 유튜브 강의 참고  (0) 2019.02.18
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
package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class baekjoon2606{
 
    static int n;
    static int t;
    static int[][] computer;
    static boolean[] visit;
    
    public static void main(String[] args){
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try{
            n = Integer.parseInt(br.readLine());
            computer = new int[n+1][n+1];
            visit = new boolean[n+1];
            t = Integer.parseInt(br.readLine());
            while(t-- >0){
                String[] temp = br.readLine().trim().split(" ");
                int a = Integer.parseInt(temp[0]);
                int b = Integer.parseInt(temp[1]);
                computer[a][b] = computer[b][a] = 1;
            }
            System.out.print(bfs(1));
        }catch(Exception e){
            e.printStackTrace();
        }
    }
    public  static int bfs(int k){
        int cnt=0;
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(k);
        while(!q.isEmpty()){
            int x = q.poll();
            visit[x] = true;
            for(int i=1;i<=n;i++){
                if(computer[x][i] == 1 && !visit[i]){
                    q.offer(i);
                    visit[i] = true;
                    cnt++;
                }
            }
        }
        return cnt;
 
    }
 
}
cs


저작자표시

'BFS,DFS_문제풀이' 카테고리의 다른 글

백준 2178 > 미로탐색 > bfs의 기본중의 기본 문제 꼭 이거 먼저 보고 시작하기 (String word = sc.nextLine(); Stirng array[] = word.split(" "); , nextY,nextY,split,visited,Integer,parseInt,LinkedList,charAt,Queue,Dot )  (0) 2019.02.26
백준 16940 > BFS스페셜 저지 > 트리에서 BFS 방문순서 올바른지 확인하기 (bfs)  (0) 2019.02.25
백준 2638 >치즈 > 자바 bfs풀이의 기초버전(Pair,LinkedList,map,dx,dy,Queue,loop,visit)  (0) 2019.02.23
DFS(C++) 나동빈님 유튜브 강의 참고  (0) 2019.02.18
BFS(C++) 나동빈님 유튜브 강의 참고  (0) 2019.02.18
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package baekjoon;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class baekjoon2638{
 
    public static int n,m,map[][], visit[][];
    public static int dx[] = {1,0,-1,0};
    public static int dy[] = {0,1,0,-1};
 
    public static void bfs(){
       Queue<Pair> q = new LinkedList<>();
       q.add(new Pair(0,0));
 
       while(!q.isEmpty()){
           Pair p = q.poll();
 
           for(int i=0;i<4;i++){
               int nx = p.x + dx[i];
               int ny = p.y + dy[i];
 
               if(nx<0 || ny<0 || nx>=n || ny>=m)
               continue;
 
               if(map[nx][ny]==0 && visit[nx][ny]==0){
                   visit[nx][ny] =1;
                   q.add(new Pair(nx,ny));
               }
               if(map[nx][ny]==1){
                   visit[nx][ny]++;
                   if(visit[nx][ny]>=2)
                   map[nx][ny] =0;
               }
           }
       }
    }
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        visit = new int[n][m];
 
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                map[i][j] = sc.nextInt();
            }
        }
        int time=0;
        boolean check = true;
        while(check){
            init_visit();//visit초기화
            bfs();
 
            //치즈가 있는지 확인
            check = false;
            loop:
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(map[i][j]!=0){
                        check = true;
                        break loop;
                    }
                }
            }
            time++;
        }
        System.out.println(time);
    }
    public static void init_visit(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                visit[i][j] = 0;
            }
        }
    }
 
    static class Pair{
        int x,y;
        Pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}
cs


저작자표시

'BFS,DFS_문제풀이' 카테고리의 다른 글

백준 2178 > 미로탐색 > bfs의 기본중의 기본 문제 꼭 이거 먼저 보고 시작하기 (String word = sc.nextLine(); Stirng array[] = word.split(" "); , nextY,nextY,split,visited,Integer,parseInt,LinkedList,charAt,Queue,Dot )  (0) 2019.02.26
백준 16940 > BFS스페셜 저지 > 트리에서 BFS 방문순서 올바른지 확인하기 (bfs)  (0) 2019.02.25
백준 2606 > 바이러스 > 자바 bfs기초문제2(BufferdReader,InputStreamReader,LinkedList,Queue,visit,Integer.parseInt,trm,split)  (0) 2019.02.24
DFS(C++) 나동빈님 유튜브 강의 참고  (0) 2019.02.18
BFS(C++) 나동빈님 유튜브 강의 참고  (0) 2019.02.18
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//깊이 우선 탐색은 너비우선 탐색과 마찬가지로 맹목적으로 각 노드 탐색할떄 주로 사용됩니다.
//너비 우선 탐색에서는 Queue가 사용 되었다면
//깊이 우선 탐색에서는 Stack을 사용하면 됩니다.
//더불어 스택을 사용하지 않아도 구현이 가능하다는 특징이 있습니다.
//컴퓨터 구조는 항상 스택의 원리를 사용하기 떄문입니다.
//컴퓨터 자체가 스택프레임이라고 해서 스택 원리가 사용되기 떄문에 스택 이용하지않고 재귀함수만으로도 깊이우선 탐색이 가능하다.
 
//재귀함수를 쓰는 이유는 stack이라는 컴퓨터 구조 처럼 쓰고 넣고를 반복하는 구조이기떄문에 사용하면 좋다.
#include<iostream>
#include<vector>
 
using namespace std;
 
//노드의 갯수는 7개
int number = 7;
//방문처리를 위해 check배열7개
int c[7];
//vector에는 총 index 8만큼 배열의 크기를 만들어주어서
vector<int> a[8];
 
//총 7개의 노드가 각각 인접한 노드를 가질수 있도록 만들어 주었다.
void dfs(int x){
    if(c[x]) return; //현재 그 노드를 방문했다면 이렇게 return해줘서 바로 함수를 끝낼 수 있도록 해준다.
    c[x] = true;//그 노드를 처음 방문하는 거라면 이렇게 방문 처리를 해주면 된다.
    cout << x << ' '; //이제 그 노드를 출력할 수 있게 해주면 된다.
    //인접 노드를 하나씩 방문을 하면서 
    for(int i=0;i<a[x].size();i++){
        //인접 노드를 대상으로 해서 dfs를 수행하면 된다.
        int y = a[x][i];
        dfs(y); //계속해서 자기와 인접한 노드를 반복한다.dfs를 수행하면서 깊이우선탐색을 안정적을 사용하게 됨.
    }
}
//DFS는 다음과 같은 간단한 알고리즘에 따라서 작동 합니다.
/*
1. 스택의 최상단 노드를 확인합니다.(가장 마지막에 들어온 노드)
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리 합니다.
3. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 뻅니다.
인접 노드 중에서 가장 작은 (낮은) 숫자가 있는 노드로 작성
*/
//차곡차곡쌓이는 스택프레임이랑 같은 원리이기떄문에 넣고 뺴고가 같은 의미
/*
void dfs(int x){
    if(c[x]) return;
    c[x] = true;
    cout << x << ' ';
    for(int i=0;i<a[x].size();i++){
        int y = a[x][i];
        dfs(y);
    }
}
*/
int main(void){
    a[1].push_back(2);
    a[2].push_back(1);
 
    a[1].push_back(3);
    a[3].push_back(1);
 
    a[2].push_back(3);
    a[3].push_back(2);
 
    a[2].push_back(4);
    a[4].push_back(2);
    
    a[2].push_back(5);
    a[5].push_back(2);
 
    a[3].push_back(6);
    a[6].push_back(3);
 
    a[3].push_back(7);
    a[7].push_back(3);
 
    a[4].push_back(5);
    a[5].push_back(4);
 
    a[6].push_back(7);
    a[7].push_back(6);
    
    dfs(1);
    return 0;
}
//이 dfs를 가지고 그래프 알고리즘을 활용할 수 있다
//이 자체로는 큰 의미가 없고 DFS를 활용해서 문제를 해결하고자 하는 것에 주안점이 두어져 있다.
//작동 원리만 빠삭하게 알아두자
//또한 스택을 직접 사용하지 않고 재귀함수를 이용해 간략하게 함수를 구현할 수 있따.
//스택에서 꺼낸 순서는  1,2,3,6,7,4,5이다.(3,6,7)먼저 돌고 (2,4,5)나중에 돈다.
cs


저작자표시

'BFS,DFS_문제풀이' 카테고리의 다른 글

백준 2178 > 미로탐색 > bfs의 기본중의 기본 문제 꼭 이거 먼저 보고 시작하기 (String word = sc.nextLine(); Stirng array[] = word.split(" "); , nextY,nextY,split,visited,Integer,parseInt,LinkedList,charAt,Queue,Dot )  (0) 2019.02.26
백준 16940 > BFS스페셜 저지 > 트리에서 BFS 방문순서 올바른지 확인하기 (bfs)  (0) 2019.02.25
백준 2606 > 바이러스 > 자바 bfs기초문제2(BufferdReader,InputStreamReader,LinkedList,Queue,visit,Integer.parseInt,trm,split)  (0) 2019.02.24
백준 2638 >치즈 > 자바 bfs풀이의 기초버전(Pair,LinkedList,map,dx,dy,Queue,loop,visit)  (0) 2019.02.23
BFS(C++) 나동빈님 유튜브 강의 참고  (0) 2019.02.18

+ Recent posts

티스토리툴바