• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

안녕하세요 질문입니다.

21.03.13 13:57 작성 조회수 79

0

안녕하세요 예전부터 강의 잘 보고 있습니다. 다름이 아니라 제가 자바만 쓰는 곳에 코테를 준비하게 되서   자바로 문제푸는 중인데 

선생님께서 강의해주신 C++을 전부 제 나름대로 자바로 바꾸는 중입니다. 근데 저 벡터 부분을 자바로 바꾸는 부분에서 막혔는데 혹시 자바에서는 선생님 코드 어떻게 써야할지 혹시 알려주시면 감사하겠습니다.(전에 자바 질문도 받아주신다는 글 봐서 질문 드립니다..) 저 벡터 로 선언한 map 부분의 map[a].push_back[b]를 자바에서 쓰려니까 구글링 해도 잘 모르겠어서 질문 드립니다.

#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
#include<vector>
using namespace std;	
int ch[30], cnt=0, n, path[30];
vector<int> map[30];
void DFS(int v, int L){
	int i, j;
	if(v==n){
		cnt++;
		for(j=0; j<L; j++){
			printf("%d ", path[j]);
		}
		puts("");
	}
	else{
		for(i=0; i<map[v].size(); i++){
			if(ch[map[v][i]]==0){
				ch[map[v][i]]=1;
				path[L]=map[v][i];
				DFS(map[v][i], L+1);
				ch[map[v][i]]=0;
			}
		}
	}
}
				
int main(){
	//freopen("input.txt", "rt", stdin);
	int m, i, j, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	ch[1]=1;
	path[0]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}

package inflearn;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Vector;

public class _66_경로탐색_인접리스트 {{

	static int []ch= new int[30];
	static int cnt = 0, n;
	static int []path= new int[30];
	//vector<int> map[30];		
	static Vector<Integer> map = new Vector<Integer>(30);
 
	static  void DFS(int v, int L){
		int i, j;
		if(v==n){
			cnt++;
			for(j=0; j<L; j++){
				System.out.printf("%d ", path[j]);
			}
			System.out.println("");
		}
		else{
			for(i=0; i<map[v].size(); i++){
				if(ch[map[v][i]]==0){
					ch[map[v][i]]=1;
					path[L]=map[v][i];
					DFS(map[v][i], L+1);
					ch[map[v][i]]=0;
				}
			}
		}
	}
					


	public static void main(String[] args) throws IOException {
			
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st; 
			Scanner sc= new Scanner(System.in);
			st = new StringTokenizer(br.readLine()," ");
			

			int n,m, i, j, a, b, c;
//			scanf("%d %d", &n, &m);
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine()," ");
			
			for(i=1; i<=m; i++){
//				scanf("%d %d", &a, &b);
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				
				map[a].push_back(b);
			}
			ch[1]=1;
			path[0]=1;
			DFS(1, 1);
			System.out.printf("%d\n", cnt);
		
		}
}

답변 1

답변을 작성해보세요.

1

안녕하세요^^

저는 인접리스트를 ArrayList로 구현합니다.

경로탐색을 인접리스트로 짜본것입니다.

import java.util.*;
class Main {
	static int n, m, answer=0;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] ch;
	public void DFS(int v){
		if(v==n) answer++;
		else{
			for(int nv : graph.get(v)){
				if(ch[nv]==0){
					ch[nv]=1;
					DFS(nv);
					ch[nv]=0;
				}
			}
		}
	}
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		graph = new ArrayList<ArrayList<Integer>>();
		for(int i=0; i<=n; i++){
			graph.add(new ArrayList<Integer>());
		}
		ch=new int[n+1];
		for(int i=0; i<m; i++){
			int a=kb.nextInt();
			int b=kb.nextInt();
			graph.get(a).add(b);
		}
		ch[1]=1;
		T.DFS(1);
		System.out.println(answer);
	}	
}

Solioquies님의 프로필

Solioquies

질문자

2021.03.14

감사합니다. 혹시 개인적인 바램이지만 자바강의는 만들생각 없으신지 여쭤봐도 될까요.

자바 강의 만들기 시작한지 1주일 정도 되었습니다. 2주 정도 더 찍어서 초반부가 완성되면 일단 오픈하고 연재식으로 할까 합니다. 그리고 할인기간 한달 안에 완성하는게 목표입니다. 

Solioquies님의 프로필

Solioquies

질문자

2021.03.15

오 자바 강의도 나온다니 기대하고 있겠습니다 감사합니다.