📃 문제
💡 문제풀이
그래프 문제이다.
그래프
그래프는 노드와 간선으로 구성된 자료구조이다.
그래프는 인접리스트와 인접행렬 2가지 방식으로 표현할 수 있다.
인접행렬은 어떤 두 정점이 연결되어 있는지를 2차원 배열에다가 나타내는 방식이다. 정점 개수가 적고(간선 수가 많거나), 노드 간 연결 여부를 자주 확인해야 하는 경우에 유용하다.
인접리스트는 어떤 정점에서 간선으로 이동할 수 있는 정점만 관리하는 표현 방식이다.
인접 행렬은 그래프의 연결 관계를 직접적으로 나타내기는 좋지만 복잡도가 높다. 그래서 보통 알고리즘을 풀 때, 그래프를 표현한다고 하면 인접리스트 방식을 주로 사용한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
// 인접리스트
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 그래프 정보 입력 받기
int N = Integer.parseInt(br.readLine()); // 정점 개수
int M = Integer.parseInt(br.readLine()); // 간선 개수
int st = Integer.parseInt(br.readLine());
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < M; i++) {
String[] line = br.readLine().split(" ");
int s = Integer.parseInt(line[0]);
int e = Integer.parseInt(line[1]);
// 양방향 간선 처리
graph.get(s).add(e);
graph.get(e).add(s);
}
System.out.println(graph);
}
}
💻 제출코드
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 그래프 정보 입력 받기
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]); // 정점 개수
int M = Integer.parseInt(line[1]); // 간선 개수
int K = Integer.parseInt(line[2]); // 시작 정점의 번호
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < M; i++) {
line = br.readLine().split(" ");
int s = Integer.parseInt(line[0]);
int e = Integer.parseInt(line[1]);
// 노드의 존재 여부 확인 후 그래프에 추가
if (!graph.containsKey(s)) {
graph.put(s, new ArrayList<>());
}
if (!graph.containsKey(e)) {
graph.put(e, new ArrayList<>());
}
graph.get(s).add(e);
graph.get(e).add(s);
}
// 방문한 노드를 기록하기 위한 배열 초기화
int[] visited = new int[N + 1];
Queue<Integer> q = new LinkedList<>();
q.add(K); // 시작 노드를 큐에 추가
int answer = 0; // 방문한 정점 개수를 저장하는 변수
int currentNode = K; // 마지막으로 방문한 정점 번호를 저장하는 변수
// 탐색할 수 있는 노드가 있을 때까지 탐색
while (!q.isEmpty()) {
currentNode = q.poll();
visited[currentNode]++; // 방문체크
answer++; // 정점을 방문할 때마다 답을 1씩 증가
// 가장 작은 정점의 번호를 다음 방문 정점으로 선택하기 위해서 후보를 정렬.
List<Integer> tempNodes = graph.get(currentNode);
if (tempNodes != null && !tempNodes.isEmpty()) {
Collections.sort(tempNodes); // 연결된 노드들을 오름차순으로 정렬
for (int nextNode : tempNodes) {
// 방문할 수 있는 정점이 나오면, 반복문을 탈출.
if (visited[nextNode] == 0) {
q.add(nextNode);
break;
}
}
}
}
System.out.println(answer + " " + currentNode); // 방문한 정점의 개수와 마지막으로 방문한 정점 번호
}
}
💭 후기
그래프 까먹어서..ㅎ 그다음 날 해설지 보고 풀었다. 다시 개념 정리했으니 이제 그래프 문제도 해결가능! 그래프 문제 좀 많이 풀어봐야겠다. 3주차 완료. 마지막 4주차까지 파이팅🌞