🔍 문제
📌 입력
첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다.
다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 N보다 작거나 같은 서로 다른 양의 정수 a와 b가 주어진다.
이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.
📌 출력
자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.
🤔 제출
모든 코드 는 BFS를 활용해서 진행 했다.
📝 첫번째 제출 코드 (시간 초과)
import java.io.*;
import java.util.*;
public class Main {
static int N,M; //정점 개수 , 간선 개수
static ArrayList<Integer>[] graphs;
static boolean[] sVisited; //학생 배열
static ArrayList<Integer> result = new ArrayList<>();
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()," ");
N = Integer.parseInt(st.nextToken()); //정점 개수
M = Integer.parseInt(st.nextToken()); //간선 개수
graphs = new ArrayList[N+1];
sVisited = new boolean[N+1]; //방문 배열
for (int i=1; i<=N; i++){
graphs[i] = new ArrayList<>();
}
for (int i=1; i<=M; i++){
StringTokenizer stD = new StringTokenizer(br.readLine()," ");
int sp = Integer.parseInt(stD.nextToken());
int ep = Integer.parseInt(stD.nextToken());
graphs[sp].add(ep); //단 방향
}
for (int i=1; i<=N; i++){
Arrays.fill(sVisited , false); //학생 방문 배열 false 초기화
longHeight(i); //자신보다 큰 학생 sVisited true
for (int j=1; j<=N; j++){
if (sVisited[j] == false){ //false 라면 자신보다 큰 키 학생은 아님
//자신을 가르키는 작은 학생인지 여부 확인
if (shortHeight(j,i)){
sVisited[j] = true;
}
else{
break;
}
}
}
if (checkResult()){
result.add(i);
}
}
bw.write(result.size() + "\n");
bw.flush();
bw.close();
}
static boolean checkResult(){
for (int i=1; i<=N; i++){
if (sVisited[i] == false){ //하나라도 false 면 자신의 정확한 순번을 알지 못함
return false;
}
}
return true;
}
static void longHeight(int start){
Queue<Integer> q = new LinkedList<>();
q.offer(start);
sVisited[start] = true;
//큰 학생 계산
while (!q.isEmpty()){
Integer cIdx = q.poll();
for (int nIdx : graphs[cIdx]){
if (sVisited[nIdx] == false){ //방문하지 않았다면
sVisited[nIdx] = true;
q.offer(nIdx);
}
}
}
}
static boolean shortHeight(int start , int target){
Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[N+1]; //방문 배열
q.offer(start);
visited[start] = true;
while (!q.isEmpty()){
Integer cIdx = q.poll();
if (cIdx == target){
return true;
}
for (int nIdx : graphs[cIdx]){
if (visited[nIdx] == false){ //방문하지 않았다면
visited[nIdx] = true;
q.offer(nIdx);
}
}
}
return false;
}
}
예제는 통과되는 것 을 확인 했으나 제출 시 시간 초과가 발생한 코드 였다.
단방향 으로 만 연결 된 그래프를 하나만 사용 했다.
학생 4번을 대상으로 문제를 진행 한다고 가정 했을때 단방향 이므로 4번 학생이 가리키는 다른 학생들은 확인 하기가 쉬웠으나(자신 보다 큰 학생들을 가리키고 있음) 자신을 가리키고 있는(4번 보다 작은 키를 가진 학생) 학생들을 판단 하기가 어려웠다.
따라서 정방향으로 탐색을 한번 진행 해서 visited 배열에 mark를 해둔 후 mark 되지 않은 학생들을 전체 순회 하면서 정방향 탐색을 계속 진행했다.
📝 두번째 제출 코드(통과)
import java.io.*;
import java.util.*;
public class Main {
static int N,M; //정점 개수 , 간선 개수
static ArrayList<Integer>[] graphs;
static ArrayList<Integer>[] rGraphs; //역방향 그래프
static ArrayList<Integer> result = new ArrayList<>();
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()," ");
N = Integer.parseInt(st.nextToken()); //정점 개수
M = Integer.parseInt(st.nextToken()); //간선 개수
graphs = new ArrayList[N+1];
rGraphs = new ArrayList[N+1];
for (int i=1; i<=N; i++){
graphs[i] = new ArrayList<>();
rGraphs[i] = new ArrayList<>();
}
for (int i=1; i<=M; i++){
StringTokenizer stD = new StringTokenizer(br.readLine()," ");
int sp = Integer.parseInt(stD.nextToken());
int ep = Integer.parseInt(stD.nextToken());
graphs[sp].add(ep); //단 방향 , 정방향 그래프
rGraphs[ep].add(sp); //역 방향 그래프 , 자신보다 작은 학생 확인 하기 위함
}
for (int i=1; i<=N; i++){
bfs(i); //자신보다 큰 학생 sVisited true
}
bw.write(result.size() + "\n");
bw.flush();
bw.close();
}
static void bfs(int start){
Queue<Integer> q = new LinkedList<>();
q.offer(start);
boolean visited[] = new boolean[N+1];
visited[start] = true;
//큰 학생 계산
while (!q.isEmpty()){
Integer cIdx = q.poll();
for (int nIdx : graphs[cIdx]){
if (visited[nIdx] == false){ //방문하지 않았다면
visited[nIdx] = true;
q.offer(nIdx);
}
}
}
q.offer(start);
//작은 학생 계산 , 역방향 그래프 사용
while (!q.isEmpty()){
Integer cIdx = q.poll();
for (int nIdx : rGraphs[cIdx]){ // 자신보다 작은 학생을 가리키는 역방향 그래프 순회
if (visited[nIdx] == false){ //방문하지 않았다면
visited[nIdx] = true;
q.offer(nIdx);
}
}
}
boolean pass = true;
for (int i=1; i<=N; i++){ //모든 학생의 키를 탐색 했는지 확인
if (visited[i] == false){
pass = false;
break;
}
}
if (pass){ //정확한 키순서를 확인 할 수 있음
result.add(start);
}
}
}자신 보다 큰 학생들을 가리키는 정방향 그래프와 자신보다 작은 학생을 가리키는 역방향 그래프를 사용했다.
결과적으로 두개의 단방향 그래프를 사용 했으며 해당 그래프를 합친다면 양방향 그래프가 될 것 이다.
양방향 그래프를 사용하면 cycle이 발생하기 때문에 단방향을 두개 사용했다.
정방향 그래프를 통해서 자신 보다 큰 키의 학생을 mark 해준 후 자신보다 작은 학생을 역방향 그래프를 통해 mark 해준다.
이후 모든 학생들이 mark 되어 있다면 정확한 자신의 키 순번을 알 수 있는 것이다.
해당 코드를 통해 정상적으로 제출을 확인 했다.
📗 정리
백준 문제를 풀고 난 후 항상 구글링 등을 통해서 다양한 코드를 확인 해본다.
분명 좋은 양질의 코드를 얻어 가면서 복기 할 수 있기에 습관 처럼 하고 있다.
이번 문제를 정상 제출 후 구글링 했을때 거의 대부분 플로이드 와샬 알고리즘을 통해서 문제를 해결 했었고 코드 양도 본인에 비해서 훨씬 간결 했다.
플로이드 와샬 알고리즘을 사용하지 않았던 이유는 단지 현재 시점에서 나는 합 배열, 슬라이딩 윈도우, 투 포인터, 그래프 이론, DFS, BFS 만 사용 할 줄 알기 때문이였다.
그래도 BFS로도 풀 수 있어서 나름 성취 있었고 후에 플로이드 와샬 알고리즘을 공부 하면 다시 한번 돌아와서 시도 해보고 싶다.
다양한 알고리즘을 알고 있는 것이 문제 해결을 쉽게 만들 수 있을 것 같다.
