JUINTINATION
프로그래머스 코딩테스트 고득점 Kit - 그래프(가장 먼 노드, 순위, 방의 개수) 본문
프로그래머스 코딩테스트 고득점 Kit - 그래프(가장 먼 노드, 순위, 방의 개수)
DEOKJAE KWON 2024. 12. 30. 18:251번 문제: 가장 먼 노드
https://school.programmers.co.kr/learn/courses/30/lessons/49189
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
각각 1부터 n까지 번호가 적혀있는 n개의 노드가 있는 그래프가 있을 때 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 한다. 여기서 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미한다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해야 한다.
접근
먼저 어떤 노드에 연결된 다른 노드 리스트를 표현하기 위한 Point 클래스를 만든다. 클래스 이름을 Node라고 짓지 않은 이유는 딱히 없고, 그냥 내가 Point라는 이름이 편해서 그런 것이다.
Point 클래스는 해당 노드의 번호를 의미하는 정수 x와 1번 노드에서 떨어진 거리를 의미하는 정수 cnt, 연결된 노드의 리스트를 의미하는 List<Point> 타입의 list가 있다. 또한 어떤 노드는 여러 개의 노드 와 연결될 수 있기 때문에 한 쪽으로 깊게 들어가는 DFS보단 BFS를 사용하는 것이 더 좋아보인다.
먼저 각각의 노드 정보를 담을 Point[] points 배열을 만들고, 각각을 초기화한다. 어떤 Point에 연결하는 다른 Point를 new Point(x)와 같이 만든다면 기존에 x번 노드에 연결된 다른 노드들에 대한 정보가 없어지기 때문이다.
bfs 메서드에서 queue에 각 노드를 삽입할 때마다 Stack<Integer> 타입의 stack에 p의 cnt값을 집어넣는다. while문이 끝나게 되면 stack에는 1번 노드와 가까운 순서대로 각 노드에 대한 거리가 들어가있을 것이다. 맨 위에 있는 값은 당연히 1번 노드와 제일 멀리 떨어진 노드에 대한 거리이므로 이 거리(stack.peek())가 최댓값(maxCnt)이다. 마지막으로 스택에서 순서대로 pop해가며 maxCnt가 아닐 때까지 answer에 1을 더한 뒤에 이를 반환한다.
코드
import java.util.*;
class Point {
private int x, cnt;
private List<Point> list;
public Point(int x, int cnt) {
this.x = x;
this.cnt = cnt;
this.list = new ArrayList<>();
}
public void add(Point point) {
list.add(point);
}
public int getX() {
return x;
}
public int getCnt() {
return cnt;
}
public void setCnt(int cnt) {
this.cnt = cnt;
}
public List<Point> getList() {
return list;
}
}
class Solution {
public int bfs(int n, Point startPoint) {
Queue<Point> queue = new LinkedList<>();
queue.add(startPoint);
boolean[] visited = new boolean[n + 1];
visited[1] = true;
Stack<Integer> stack = new Stack<>();
while (!queue.isEmpty()) {
Point p = queue.poll();
for (Point e : p.getList()) {
if (!visited[e.getX()]) {
visited[e.getX()] = true;
e.setCnt(p.getCnt() + 1);
queue.offer(e);
stack.push(e.getCnt());
}
}
}
int maxCnt = stack.peek(), answer = 0;
while (!stack.isEmpty()) {
if (stack.pop() == maxCnt) {
answer++;
} else {
break;
}
}
return answer;
}
public int solution(int n, int[][] edge) {
Point[] points = new Point[n + 1];
for (int i = 1; i <= n; i++) {
points[i] = new Point(i, 0);
}
for (int[] e : edge) {
int a = e[0], b = e[1];
points[a].add(points[b]);
points[b].add(points[a]);
}
return bfs(n, points[1]);
}
}2번 문제: 순위
https://school.programmers.co.kr/learn/courses/30/lessons/49191
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지의 번호를 받는다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이길 때 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 했지만, 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해야 한다.
접근
이 문제는 플로이드 워셜 알고리즘을 응용하여 풀 수 있다. 플로이드 워셜 알고리즘을 사용할 수 있는 조건은 음의 사이클이 존재하지 않는 경우인데, 권투선수 A, B, C가 있을 때 A가 B를 이기고, B가 C를 이길 때 C가 A를 이길 수 있는 경우는 존재하지 않기 때문에 조건이 성립한다.
플로이드 워셜 알고리즘을 사용하기 위한 정수 배열 arr[n][n]을 만든다. 임의의 선수 번호 x, y가 있을 때 arr[x][y]가 1이라면 x번 선수가 y번 선수를 이긴다는 뜻이고, -1이라면 진다는 뜻이다. arr[x][y]가 1일 때 arr[y][x]는 반드시 -1이다.
먼저 주어진 정보 results에 대해 arr 배열을 1 또는 -1로 초기화한다. 그리고 삼중 for문에서 i, j, k는 모두 0부터 n - 1까지 순회하며, i번 선수가 k번 선수를 이기고(arr[i][k] == 1) k번 선수가 j번 선수를 이긴다면(arr[k][j] == 1) i번 선수는 j번 선수를 반드시 이긴다(arr[i][j] = 1, arr[j][i] = -1). 반대의 경우도 마찬가지이다(arr[i][k] == -1, arr[k][j] == -1 -> arr[i][j] = -1, arr[j][i] = 1).
구할 수 있는 모든 경우에 대해 arr 배열을 채웠다면, 각 행에 대해 값이 0이 아닌 열(승부를 알 수 있는 경우)의 개수를 구한다. 그 개수가 n - 1이라면 순위를 알 수 있다는 뜻이므로 이 경우에 answer에 1을 더하고, 마지막에 이를 반환한다.
코드
class Solution {
public int floydWarshall(int n, int[][] results) {
int[][] arr = new int[n][n];
for (int[] result : results) {
int a = result[0] - 1;
int b = result[1] - 1;
arr[a][b] = 1;
arr[b][a] = -1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (arr[i][k] == 1 && arr[k][j] == 1) {
arr[i][j] = 1;
arr[j][i] = -1;
}
if (arr[i][k] == -1 && arr[k][j] == -1) {
arr[i][j] = -1;
arr[j][i] = 1;
}
}
}
}
int answer = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
if (arr[i][j] != 0) {
cnt++;
}
}
if (cnt == n - 1) {
answer++;
}
}
return answer;
}
public int solution(int n, int[][] results) {
return floydWarshall(n, results);
}
}3번 문제: 방의 개수
https://school.programmers.co.kr/learn/courses/30/lessons/49190
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋는다.
사방이 막혀있으면 방 하나로 새며, 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성해야 한다.
접근
방이 될 수 있는 조건에는 위의 그림과 같이 일단 그래프가 순환해야 한다. 순환하는지 여부를 체크하는 방법으로 어떤 노드에 방문한 적이 있으며, 이동 경로에 있는 간선에 방문한 적이 없어야 한다. 이를 위해 각각의 visited 배열이 필요하다.
이때 간선의 방문 여부를 체크하는 visited 배열에 지나온 간선 뿐만 아니라 반대 간선에도 방문 체크를 해줘야 하는데 그 이유는 아래와 같다.
이 그림에서 [0, 2, 4, 6]에 의해 이미 방이 하나가 카운트됐지만, 그 다음 [2]를 진행하면서 어떤 노드(0, 1)에 방문한 적이 있으며, 이동 경로에 있는 간선에 방문한 적이 없어야 한다는 조건이 성립되기 때문에 하나가 더 카운트된다. 때문에 이를 방지하기 위해 지나온 간선에 대해 반대 간선도 체크를 해줘야 한다. 양방향 간선이라고 생각하면 될 것 같다.
배열의 인덱스는 음수를 가질 수 없기 때문에 가장 위쪽에 있는 좌표의 행값과 가장 왼쪽에 있는 좌표의 열값을 구하여, 이를 기준으로 잡아야 한다. 이때 각 좌표에 대해 2배를 해줘야 하는데, 그 이유를 그림으로 그려보면 아래와 같다.
위의 그림을 보면 분명이 방은 2개지만, 1개로 카운트된다. 그 이유는 중간에 (0.5, 0.5)는 노드로 치지 않기 때문인데, 그래서 이 문제를 방지하기 위해 2배로 늘려서 (0.5x, 0.5y)를 (x, y)로 고치는 것이다.
boolean[][] visitedNode 배열은 각 노드의 방문 여부만 체크하면 되기 때문에 이차원 배열로, boolean[][][] visitedEdge 배열은 visitedEdge[x][y][z]에 대해 (x, y) 좌표로 z번 방향으로 이동했다는 의미를 가지므로 삼차원 배열로 만든다.
주어진 arrows 배열에 맞게 그림을 그려나가는데, 이때 좌표를 2배로 늘렸기 때문에 2번씩 실행한다. 현재 좌표의 행(r), 열(c)과 그 다음 좌표의 행(nr), 열(nc)을 구하고, 방의 조건이 성립되면 answer에 1을 더한다. 각각을 방문처리한 뒤에 현재 좌표를 그 다음 좌표로 이동(r = nr, c = nc)시킨다. 모든 arrows에 대해 위를 실행했다면 answer를 반환한다.
코드1(메모리 초과)
class Solution {
public int solution(int[] arrows) {
int[][] afterArrows = new int[arrows.length + 1][2];
int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1}, dc = {0, 1, 1, 1, 0, -1, -1, -1};
for (int i = 0; i < arrows.length; i++) {
afterArrows[i + 1][0] = afterArrows[i][0] + dr[arrows[i]] * 2;
afterArrows[i + 1][1] = afterArrows[i][1] + dc[arrows[i]] * 2;
}
int minR = 0, minC = 0;
for (int[] afterArrow : afterArrows) {
minR = Math.min(minR, afterArrow[0]);
minC = Math.min(minC, afterArrow[1]);
}
int maxR = 0, maxC = 0;
for (int[] afterArrow : afterArrows) {
afterArrow[0] -= minR;
afterArrow[1] -= minC;
maxR = Math.max(maxR, afterArrow[0]);
maxC = Math.max(maxC, afterArrow[1]);
}
boolean[][] visitedNode = new boolean[maxR + 1][maxC + 1];
int r = -minR, c = -minC;
visitedNode[r][c] = true;
int answer = 0;
boolean[][][] visitedEdge = new boolean[maxR + 1][maxC + 1][8];
for (int arrow : arrows) {
for (int i = 0; i < 2; i++) {
int nr = r + dr[arrow], nc = c + dc[arrow];
if (visitedNode[nr][nc] && !visitedEdge[nr][nc][arrow]) {
answer++;
}
visitedNode[nr][nc] = true;
visitedEdge[nr][nc][arrow] = true;
visitedEdge[r][c][(arrow + 4) % 8] = true;
r += dr[arrow];
c += dc[arrow];
}
}
return answer;
}
}마지막 2개의 테스트 케이스에 대해 메모리 초과가 발생했다. 이 코드에서 메모리를 가장 많이 사용하는 부분은 삼차원 배열인 visitedEdge라는 생각이 들어 이를 해결하기 위해 Set<String> 타입의 visitedEdgeSet을 사용했다.
코드2(visitedEdgeSet)
import java.util.*;
class Solution {
public int solution(int[] arrows) {
int[][] afterArrows = new int[arrows.length + 1][2];
int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1}, dc = {0, 1, 1, 1, 0, -1, -1, -1};
for (int i = 0; i < arrows.length; i++) {
afterArrows[i + 1][0] = afterArrows[i][0] + dr[arrows[i]] * 2;
afterArrows[i + 1][1] = afterArrows[i][1] + dc[arrows[i]] * 2;
}
int minR = 0, minC = 0;
for (int[] afterArrow : afterArrows) {
minR = Math.min(minR, afterArrow[0]);
minC = Math.min(minC, afterArrow[1]);
}
int maxR = 0, maxC = 0;
for (int[] afterArrow : afterArrows) {
afterArrow[0] -= minR;
afterArrow[1] -= minC;
maxR = Math.max(maxR, afterArrow[0]);
maxC = Math.max(maxC, afterArrow[1]);
}
boolean[][] visitedNode = new boolean[maxR + 1][maxC + 1];
int r = -minR, c = -minC;
visitedNode[r][c] = true;
int answer = 0;
Set<String> visitedEdgeSet = new HashSet<>();
for (int arrow : arrows) {
for (int i = 0; i < 2; i++) {
int nr = r + dr[arrow], nc = c + dc[arrow];
if (visitedNode[nr][nc] && !visitedEdgeSet.contains(r + ", " + c + " -> " + nr + ", " + nc)) {
answer++;
}
visitedNode[nr][nc] = true;
visitedEdgeSet.add(r + ", " + c + " -> " + nr + ", " + nc);
visitedEdgeSet.add(nr + ", " + nc + " -> " + r + ", " + c);
r += dr[arrow];
c += dc[arrow];
}
}
return answer;
}
}visitedEdgeSet에는 r, c -> nr, nc와 같은 형식으로 간선에 대한 방문처리를 진행한다. int[]나 int[][]와 같은 숫자를 저장하는 Set이 아니라 String을 저장하는 Set을 사용하는 이유는 contains 메서드를 사용할 때 String 타입은 equals 메서드를 사용하여 값을 비교하지만, 배열 타입은 equals 메서드를 사용하여 값을 비교하면 인스턴스 자체로 비교하기 때문에 에러가 발생할 수 있기 때문이다. 물론 관련 메서드를 오버라이딩하면 사용할 수는 있다.
코드3(visitedNodeSet, visitedEdgeSet)
import java.util.*;
class Solution {
public int solution(int[] arrows) {
int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};
Set<String> visitedNodeSet = new HashSet<>();
Set<String> visitedEdgeSet = new HashSet<>();
visitedNodeSet.add("0, 0");
int r = 0, c = 0;
int answer = 0;
for (int arrow : arrows) {
for (int i = 0; i < 2; i++) {
int nr = r + dr[arrow], nc = c + dc[arrow];
if (visitedNodeSet.contains(nr + ", " + nc) && !visitedEdgeSet.contains(r + ", " + c + " -> " + nr + ", " + nc)) {
answer++;
}
visitedNodeSet.add(nr + ", " + nc);
visitedEdgeSet.add(r + ", " + c + " -> " + nr + ", " + nc);
visitedEdgeSet.add(nr + ", " + nc + " -> " + r + ", " + c);
r = nr;
c = nc;
}
}
return answer;
}
}깃허브에는 좌표를 2배로 늘려야 한다고 생각한 것을 기억하고 싶어서 코드2로 올려놨지만(나중에 의미가 없다고 판단되면 코드3으로 수정할 수도 있다), 좌표값 자체도 Set에 저장하여 코드를 더 간결하게 바꿀 수 있다. 어쨌든 어떤 노드에 대해 방문여부만 확인하면 되기 때문에 방문한 노드의 좌표를 String 타입으로 변환하여 visitedNodeSet에 저장하고 contains 메서드를 사용할 수 있다.
결론
그래프라고 해서 DFS/BFS 알고리즘 파트가 이미 있으니까 당연히 다익스트라나 최단거리를 구하는 알고리즘 문제가 있을 줄 알았다. 1번부터 BFS 알고리즘을 사용하여 풀 수 있는 문제가 나와서 여기서 굳이 다익스트라 알고리즘을 써야하나 고민했고, 3번 문제는 완전 새로운 유형의 사고 문제가 나와서 당황했다.
그래도 어떤 알고리즘을 써야겠다고 예상되지 않는 문제를 포기하지 않고 풀어내서 뿌듯했다. 코딩 테스트 실전에도 이런 경험을 살려 좋은 결과가 있으면 좋겠다.