[伯俊]1976旅行に行こうjava
1.質問
2.コード import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
백준 1976 문제
플로이드-와샬을 적용하면 간단하게 풀립니다.
주의할점 : 자기 자신으로 가는 것이 가능하다.
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[][] able = new int[N][N];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
able[i][j] = Integer.parseInt(st.nextToken());
if(i==j) able[i][j] = 1;
}
}
//플로이드 와샬
for(int k=0; k<N; k++) {
for(int i=0; i<N; i++) {
if(k==i) continue;
for(int j=0; j<N; j++) {
if(j==k || j==i) continue;
if(able[i][k]+able[k][j]==2) {
able[i][j] = 1;
}
}
}
}
boolean result = true;
StringTokenizer st= new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = 0;
for(int i=0; i<M-1; i++) {
end = Integer.parseInt(st.nextToken());
if(able[start-1][end-1]==0) {
result = false;
break;
}
start = end;
}
if(result) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}
3.Review
フロイド・ワッシャーを適用すれば問題を解決できます.
問題の条件の下で、次の旅行先を出発地と同じように行けると見なすべきだ.
Reference
この問題について([伯俊]1976旅行に行こうjava), 我々は、より多くの情報をここで見つけました
https://velog.io/@hakka_ame/백준-1976-여행-가자.java
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
백준 1976 문제
플로이드-와샬을 적용하면 간단하게 풀립니다.
주의할점 : 자기 자신으로 가는 것이 가능하다.
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[][] able = new int[N][N];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
able[i][j] = Integer.parseInt(st.nextToken());
if(i==j) able[i][j] = 1;
}
}
//플로이드 와샬
for(int k=0; k<N; k++) {
for(int i=0; i<N; i++) {
if(k==i) continue;
for(int j=0; j<N; j++) {
if(j==k || j==i) continue;
if(able[i][k]+able[k][j]==2) {
able[i][j] = 1;
}
}
}
}
boolean result = true;
StringTokenizer st= new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = 0;
for(int i=0; i<M-1; i++) {
end = Integer.parseInt(st.nextToken());
if(able[start-1][end-1]==0) {
result = false;
break;
}
start = end;
}
if(result) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}
3.Review
フロイド・ワッシャーを適用すれば問題を解決できます.
問題の条件の下で、次の旅行先を出発地と同じように行けると見なすべきだ.
Reference
この問題について([伯俊]1976旅行に行こうjava), 我々は、より多くの情報をここで見つけました
https://velog.io/@hakka_ame/백준-1976-여행-가자.java
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
Reference
この問題について([伯俊]1976旅行に行こうjava), 我々は、より多くの情報をここで見つけました https://velog.io/@hakka_ame/백준-1976-여행-가자.javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol