-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
안녕하세요 질문입니다.
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
김태원
지식공유자2021.03.13
안녕하세요^^
저는 인접리스트를 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);
}
}
김태원
지식공유자2021.03.15
자바 강의 만들기 시작한지 1주일 정도 되었습니다. 2주 정도 더 찍어서 초반부가 완성되면 일단 오픈하고 연재식으로 할까 합니다. 그리고 할인기간 한달 안에 완성하는게 목표입니다.
답변 1