개발자 톡
어디서 잘못되엇느지 모르겟습니다...
- 등록일
- 2024-02-02 20:05:57
- 조회수
- 635
- 작성자
- mansa0805
dfs로 모든 경로를 찾고
각 경로를 LCS로 행복지수의 최대 값을 구하도록 구현하였습니다. 어디가 잘못되었을까요?
import java.io.*;
import java.util.*;
public class Main {
public static String[][] tree;
public static boolean[][] visited;
public static int N;
public static ArrayList<String> ways = new ArrayList<>();
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());
tree = new String[N][N];
visited = new boolean[N][N];
int M = Integer.parseInt(st.nextToken());
String s = br.readLine();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
String c = st.nextToken();
tree[u-1][v-1] = c;
tree[v-1][u-1] = c;
}
//경로 dfs로 찾기
StringBuilder way = new StringBuilder();
dfs(0,way);
//각 경로 마다 dp로(LCS 알고리즘) 최대 행복지수 찾기
int max = 0;
for (int i = 0; i < ways.size(); i++) {
int lcs = LCS(s,ways.get(i));
if (lcs > max) {
max = lcs;
}
}
System.out.println(max);
br.close();
}
public static void dfs(int cur, StringBuilder way) {
if(isTerminalNode(cur)) {
ways.add(way.toString());
return;
}
for (int i = 0; i < N; i++) {
if (!visited[cur][i] && tree[cur][i] != null) {
visited[cur][i] = true;
visited[i][cur] = true;
way.append(tree[cur][i]);
dfs(i,way);
way.delete(way.length() - 1, way.length());
visited[cur][i] = false;
visited[i][cur] = false;
}
}
}
public static boolean isTerminalNode(int number) {
if(number == 0) {
return false;
}
int count = 0;
for (int i = 0; i < N; i++) {
if (tree[number][i] != null) {
count++;
}
}
if (count == 1) {
return true;
}
return false;
}
public static int LCS(String a, String b) {
int dp[][] = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= b.length(); j++) {
if (a.charAt(i-1) == b.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[a.length()][b.length()];
}
}