JUINTINATION
프로그래머스 코딩테스트 고득점 Kit - 깊이/너비 우선 탐색(타겟 넘버, 네트워크, 게임 맵 최단거리, 단어 변환, 아이템 줍기, 여행경로, 퍼즐 조각 채우기) 본문
프로그래머스 코딩테스트 고득점 Kit - 깊이/너비 우선 탐색(타겟 넘버, 네트워크, 게임 맵 최단거리, 단어 변환, 아이템 줍기, 여행경로, 퍼즐 조각 채우기)
DEOKJAE KWON 2024. 12. 26. 18:521번 문제: 타겟 넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
n개의 음이 아닌 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
- -1+1+1+1+1 = 3
- +1-1+1+1+1 = 3
- +1+1-1+1+1 = 3
- +1+1+1-1+1 = 3
- +1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해야 한다.
접근
numbers 배열에 있는 모든 값들에 대해 더하거나 빼서 target을 만들 수 있는 방법의 수를 반환해야 한다. 이 방법의 수를 의미하는 answer는 0부터 시작하고, dfs를 활용하여 깊이를 의미하는 매개변수 dpth를 numbers 배열에 접근하는 인덱스로 생각하여 0부터 시작하는 매개변수 sum에 numbers[dpth]를 더하거나 빼며 재귀적으로 메서드를 실행한다.
dpth가 numbers 배열의 길이가 되었다면 sum이 target과 같은지 확인하고, 같다면 answer에 1을 더하고 반환한다. 마지막에 dfs(numbers, target, 0, 0)을 실행한 뒤 answer를 반환한다.
코드
class Solution {
private int answer = 0;
public void dfs(int[] numbers, int target, int dpth, int sum) {
if (dpth == numbers.length){
if (sum == target) answer++;
return;
}
sum += numbers[dpth];
dfs(numbers, target, dpth + 1, sum);
sum -= 2 * numbers[dpth];
dfs(numbers, target, dpth + 1, sum);
}
public int solution(int[] numbers, int target) {
dfs(numbers, target, 0, 0);
return answer;
}
}2번 문제: 네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
이 문제에서 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미한다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있으므로 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성해야 한다.
접근
먼저 어떤 컴퓨터에 연결된 다른 컴퓨터 리스트를 표현하기 위한 Point 클래스를 만든다. 클래스 이름을 Computer라고 짓지 않은 이유는 딱히 없고, 그냥 내가 Point라는 이름이 편해서 그런 것이다.
Point 클래스는 해당 컴퓨터의 번호를 의미하는 정수 x와 연결된 컴퓨터의 리스트를 의미하는 List<Point> 타입의 list가 있다. 또한 어떤 컴퓨터는 여러 개의 컴퓨터와 연결될 수 있기 때문에 한 쪽으로 깊게 들어가는 DFS보단 BFS를 사용하는 것이 더 좋아보인다.
먼저 각각의 컴퓨터 정보를 담을 Point[] points 배열을 만들고, 각각을 초기화한다. 어떤 Point에 연결하는 다른 Point를 new Point(x)와 같이 만든다면 기존에 x번 컴퓨터에 연결된 다른 컴퓨터들에 대한 정보가 없어지기 때문이다.
points 배열을 초기화하고, computers 배열에 있는 정보를 기반으로 컴퓨터들을 연결한다. 그리고 visited 배열을 초기화하고, for문에서 i번 컴퓨터를 방문한 적이 없다면 bfs(points[i])를 실행한다.
bfs(Point start) 메서드는 start 컴퓨터에 연결된 모든 컴퓨터를 순회하며 방문처리를 하는 역할이라고 보면 된다. 그러면 하나의 네트워크에 있는 모든 컴퓨터들이 방문처리가 되며, 위의 for문에서 같은 네트워크에 있다면 visited[i]는 true여서 bfs 메서드를 실행하지 않을 것이다. 그래서 bfs 메서드를 실행할 때마다 answer에 1을 더해주며, 마지막에 answer를 반환한다.
코드
import java.util.*;
class Point {
private int x;
private List<Point> list;
public Point(int x) {
this.x = x;
this.list = new ArrayList<>();
}
public void add(Point point) {
list.add(point);
}
public int getX() {
return x;
}
public List<Point> getList() {
return list;
}
}
class Solution {
private boolean[] visited;
public void bfs(Point start) {
Queue<Point> queue = new LinkedList<>();
queue.add(start);
visited[start.getX()] = true;
while (!queue.isEmpty()) {
Point p = queue.poll();
for (Point next : p.getList()) {
if (!visited[next.getX()]) {
visited[next.getX()] = true;
queue.add(next);
}
}
}
}
public int solution(int n, int[][] computers) {
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
points[i] = new Point(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < computers[i].length; j++) {
if (computers[i][j] == 1) {
points[i].add(points[j]);
}
}
}
int answer = 0;
visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
bfs(points[i]);
answer++;
}
}
return answer;
}
}3번 문제: 게임 맵 최단거리
https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시이다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길이다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있다.
첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했다.
두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했다. 위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법이다.
만약, 상대 팀이 위와 같이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있다. 게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해야 한다. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해야 한다.
접근
캐릭터는 상, 하, 좌, 우 이렇게 4가지 방향으로 갈 수 있으니 한 쪽으로 깊게 들어갔다가 돌아오는 DFS보단 BFS가 유리할 것이다. 먼저 게임 맵의 행(r), 열(c), 그리고 시작 지점(0, 0)부터 해당 행열(r, c)에 도달하기까지의 칸의 개수(cnt)를 필드로 갖는 Point 클래스를 만든다.
bfs 메서드에서는 시작지점에 대한 Point 인스턴스(new Point(0, 0, 1))를 Queue<Point> 타입의 queue에 삽입하고, 어떤 행렬(x, y)에 대한 방문 여부를 체크하는 boolean[][] visited 배열을 만들어 visited[0][0]을 true로 초기화한다.
이후에 while문을 통해 queue가 빌 때까지 하나씩 poll하며 그 다음 상, 하, 좌, 우로 이동할 수 있는지 확인하고, visited 배열에 체크한 뒤 queue에 삽입하는 과정을 반복한다.
상대팀 진영에 도착하는 가장 빠른 방법을 찾아야 하므로 가장 먼저 while문 안에서 (n - 1, m - 1)에 도착하는 poll된 Point p의 cnt를 반환한다. while문이 끝나도 메서드가 종료되지 않았다면 -1를 반환한다.
코드
import java.util.*;
class Point {
private int r, c, cnt;
public Point(int r, int c, int cnt) {
this.r = r;
this.c = c;
this.cnt = cnt;
}
public int getR() {
return r;
}
public int getC() {
return c;
}
public int getCnt() {
return cnt;
}
}
class Solution {
public int bfs(int[][] maps, int n, int m) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(0, 0, 1));
boolean[][] visited = new boolean[n][m];
visited[0][0] = true;
int[] dr = {1, 0, -1, 0}, dc = {0, -1, 0, 1};
while (!queue.isEmpty()) {
Point p = queue.poll();
if (p.getR() == n - 1 && p.getC() == m - 1) {
return p.getCnt();
}
for (int i = 0; i < 4; i++) {
int nr = p.getR() + dr[i], nc = p.getC() + dc[i];
if (0 <= nr && nr < n && 0 <= nc && nc < m) {
if (maps[nr][nc] == 1 && !visited[nr][nc]) {
visited[nr][nc] = true;
queue.add(new Point(nr, nc, p.getCnt() + 1));
}
}
}
}
return -1;
}
public int solution(int[][] maps) {
int n = maps.length, m = maps[n - 1].length;
return bfs(maps, n, m);
}
}4번 문제: 단어 변환
https://school.programmers.co.kr/learn/courses/30/lessons/43163
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
두 개의 단어 begin, target과 단어의 집합 words가 있을 떄 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 한다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해야 한다. 또한 변환할 수 없는 경우에는 0을 return해야 한다.
접근
어떤 단어에서도 바꿀 수 있는 알파벳은 여러 개가 있으므로 위의 문제와 마찬가지로 DFS보단 BFS가 더 유리할 것 같다. 먼저 현재 문자열(str)과 처음 단어(begin)부터 현재 단어까지 words를 통해 바뀐 횟수(cnt)를 필드로 갖는 Point 클래스를 만들고, bfs 메서드에서 Queue<Point> 타입의 queue에 new Point(begin, 0)을 삽입한다. 또한 words에 있는 어떤 단어를 반복해서 순회할 수도 있으므로, 어떤 단어로 바꾼 적이 있는지 여부를 체크하는 boolean[] visited 배열을 만들어야 한다.
이후에는 while문 안에서 queue가 빌 때까지 poll된 Point p가 words 배열의 i번째 문자열로 바꾼적 없다면 바꿀 수 있는지 체크한다. 바꿀 수 있다면 visited[i]를 true로 체크하고, 바뀐 문자열과 p의 cnt에 1을 더한 값에 대한 Point 인스턴스를 queue에 넣는 과정을 반복한다. p의 str이 target과 같다면 p의 cnt를 반환하고, while문이 끝나도 메서드가 종료되지 않았다면 0을 반환한다.
코드
import java.util.*;
class Point {
private String str;
private int cnt;
public Point(String str, int cnt) {
this.str = str;
this.cnt = cnt;
}
public String getStr() {
return str;
}
public int getCnt() {
return cnt;
}
}
class Solution {
public int bfs(String begin, String target, String[] words) {
Queue<Point> queue = new LinkedList<>();
boolean[] visited = new boolean[words.length];
queue.offer(new Point(begin, 0));
while (!queue.isEmpty()) {
Point p = queue.poll();
if (p.getStr().equals(target)) {
return p.getCnt();
}
for (int i = 0; i < words.length; i++) {
if (!visited[i]) {
int cnt = 0;
for (int j = 0; j < words[i].length(); j++) {
if (p.getStr().charAt(j) != words[i].charAt(j)) {
cnt++;
}
}
if (cnt == 1) {
visited[i] = true;
queue.offer(new Point(words[i], p.getCnt() + 1));
}
}
}
}
return 0;
}
public int solution(String begin, String target, String[] words) {
return bfs(begin, target, words);
}
}5번 문제: 아이템 줍기
https://school.programmers.co.kr/learn/courses/30/lessons/87694
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 한다.
지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동한다. 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 된다.
단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없다.
즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없으며, 다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없다.
한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없다.
지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해야 한다.
접근
위의 문제와 마찬가지로 상, 하, 좌, 우 이렇게 4가지 방향으로 갈 수 있으니 한 쪽으로 깊게 들어갔다가 돌아오는 DFS보단 BFS가 유리할 것이다. 그리고 맵의 크기를 2배로 늘려야 하는데, 그 이유는 다음과 같다.
BFS를 하면서 테두리를 따라가는 중에 내 테두리가 아닌 옆의 테두리로 셀 수도 있기 때문인데, 1번 예제를 보면서 맵을 그려본다면 이해할 수 있을 것이다.
이렇게 보면 딱히 문제될 것 같지 않지만, 이는 우리가 그림을 선으로 그리기 때문이다. 하지만 컴퓨터에서는 좌표로 그려가기 때문에 xy 좌표 기준으로 (3, 5)와 (3, 6)같은 부분이 붙어 있다. 아래는 이를 표현한 그림이다.
분명히 선으로 그리면 붙어있지 않은데, 이렇게 좌표로 그리니 붙어있는 것을 알 수 있다. 그래서 맵의 크기를 2배로 늘려 위 현상을 방지하고, 마지막에 값을 반환하기 전에 나누기 2를 진행하면 된다.
맨 바깥쪽 테두리 이외에 다른 곳은 이동할 수 없기 때문에 해당 부분에 대한 필터링을 진행해야 한다. 최대 50X50 사이즈의 맵을 2배로 늘린 배열 map[101][101]를 만들고, rectangle 배열에 있는 여러 좌표 (x1, y1), (x2, y2)에 대해 테두리만 1을 map에 표기하고, 나머지 내부는 -1로 표기한다. 이때 i가 x1부터 x2까지, j가 y1부터 y2까지 순회하는 이중 for문에서 map[i][j]가 -1이 아닐 때만 위를 수행한다.
bfs 메서드에서의 이동을 포함한 나머지 과정은 위의 문제와 유사하므로, 설명은 생략하도록 하겠다.
코드
import java.util.*;
class Point {
private int x, y, cnt;
public Point(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getCnt() {
return cnt;
}
}
class Solution {
public int bfs(int[][] map, int characterX, int characterY, int itemX, int itemY) {
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(characterX, characterY, 0));
boolean[][] visited = new boolean[101][101];
visited[characterX][characterY] = true;
int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
while (!queue.isEmpty()) {
Point p = queue.poll();
int x = p.getX(), y = p.getY();
if (x == itemX && y == itemY) {
return p.getCnt() / 2;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (0 <= nx && nx < 101 && 0 <= ny && ny < 101) {
if (!visited[nx][ny] && map[nx][ny] == 1) {
visited[nx][ny] = true;
queue.offer(new Point(nx, ny, p.getCnt() + 1));
}
}
}
}
return -1;
}
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
int[][] map = new int[101][101];
for (int[] rect : rectangle) {
int x1 = rect[0] * 2, y1 = rect[1] * 2, x2 = rect[2] * 2, y2 = rect[3] * 2;
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <=y2; j++) {
if (map[i][j] != -1) {
if (i == x1 || i == x2 || j == y1 || j == y2) {
map[i][j] = 1;
} else {
map[i][j] = -1;
}
}
}
}
}
return bfs(map, characterX * 2, characterY * 2, itemX * 2, itemY * 2);
}
}6번 문제: 여행경로
https://school.programmers.co.kr/learn/courses/30/lessons/43164
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
주어진 항공권을 모두 이용하여 여행경로를 짜려고 하며, 여행경로는 항상 "ICN" 공항에서 출발한다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해야 한다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미이며, 주어진 항공권은 모두 사용해야 한다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 반환하며, 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.
접근
이 문제는 여행경로를 순서대로 이어붙여서 출력해야 하기 때문에 재귀적으로 현재 경로에 다음 공항으로 가는 경로를 이어붙일 수 있는 DFS가 유리할 것이다.
dfs 메서드는 깊이를 의미하는 int dpth와 tickets 배열, 그리고 지금까지의 여행 경로를 저장한 StringBuilder routeSb와 현재 공항을 의미하는 String now를 매개변수로 갖는다. 처음 시작하는 공항은 "ICN"이므로, dfs(0, tickets, new StringBuilder("ICN"), "ICN")로 시작한다.
tickets 배열에 있는 ticket 배열을 사용했는지 여부를 체크하는 boolean[] visited 배열이 필요하며, 가능한 모든 경로들을 저장할 List<String> list 리스트도 필요하다.
dfs 메서드에서 tickets 배열을 순회하며 i번 인덱스의 티켓을 사용한 적이 없다면 현재 위치(now)와 해당 티켓의 출발 공항(ticketFrom)을 비교한다. 일치한다면 해당 티켓을 사용했다고 체크하고 dpth에 1을 더하고 routeSb에 " ticketTo"를 append하고, now를 ticketTo로 바꿔 재귀적으로 dfs 메서드를 실행한다. 이 메서드의 실행이 종료되면 routeSb에 있던 " "와 공항 이름을 지우기 위해 뒤의 4글자를 지우고, 그 다음 dfs 메서드에서 체크중이던 티켓을 다시 사용할 수 있도록 방문 체크를 해제한다. dpth가 tickets의 길이와 같아진다면 모든 공항을 여행한 것으로 list에 routeSb를 String 타입으로 변환하여 저장한다.
위 과정이 모두 끝난 마지막에는 list를 Collections.sort로 정렬하고, StringTokenizer를 사용하여 list의 가장 첫 번째 여행경로를 배열에 담아 반환한다.
코드
import java.util.*;
class Solution {
public List<String> list = new ArrayList<>();
public boolean[] visited;
public void dfs(int dpth, String[][] tickets, StringBuilder routeSb, String now) {
if (dpth == tickets.length) {
list.add(routeSb.toString());
return;
}
for (int i = 0; i < tickets.length; i++) {
if (!visited[i]) {
String ticketFrom = tickets[i][0], ticketTo = tickets[i][1];
if (ticketFrom.equals(now)) {
visited[i] = true;
dfs(dpth + 1, tickets, routeSb.append(" ").append(ticketTo), ticketTo);
routeSb.delete(routeSb.length() - 4, routeSb.length());
visited[i] = false;
}
}
}
}
public String[] solution(String[][] tickets) {
visited = new boolean[tickets.length];
dfs(0, tickets, new StringBuilder("ICN"), "ICN");
Collections.sort(list);
String[] answer = new String[tickets.length + 1];
StringTokenizer st = new StringTokenizer(list.get(0), " ");
for (int i = 0; i < answer.length; i++) {
answer[i] = st.nextToken();
}
return answer;
}
}7번 문제: 퍼즐 조각 채우기
https://school.programmers.co.kr/learn/courses/30/lessons/84021
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양이다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채워야 한다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시이다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타낸다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타낸다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우이다.
- 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생긴다.
- 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생긴다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습이다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있다. 현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해야 한다.
접근
game_board에 있는 빈 칸 혹은 table에 있는 퍼즐 조각을 모두 조각이라고 용어를 통일했을 때 모든 조각에 대해 상, 하, 좌, 우로 탐색하기 위해 DFS가 아닌 BFS를 사용했다. 어떤 조각을 탐색할 때 처음 탐색하는 좌표를 기준으로 얼마나 떨어져있는지 구하는 것이 목표이다. 그래야 table에 있는 퍼즐 조각을 회전하기 쉬울 것이다.
먼저 현재 조각을 탐색하는 위치의 행(r)과 열(c)을 필드로 갖는 Point 클래스를 만들고, 정렬에 필요한 Comparable<Point>를 구현하여 compareTo(T o) 메서드를 오버라이딩한다. 정렬이 필요한 이유는 아래에서 설명하겠다.
이 문제에서 사용한 bfs 메서드는 보통의 bfs 메서드와 같이 Queue<Point> 타입의 queue를 가지고, 각각의 조각이 몇 칸인지 모르기 때문에 모든 칸을 연결하기 위해 각 조각을 List<Point> 타입의 list로 저장한다. 또한 이 bfs 메서드의 목표는 위에서 언급하였듯이 처음 탐색하는 좌표를 기준으로 얼마나 떨어져있는지 구하는 것이기 때문에 처음에 queue에는 new Point(r, c)를 삽입하지만 list에는 new Point(0, 0)을 삽입한다. 이와 같은 원리로 while문 안에서 queue에는 new Point(nr, nc))를 삽입하지만, list에는 new Point(nr - r, nc - c)를 삽입한다.
이 bfs 메서드에서 이동할 수 있는 곳은 boardTable[nr][nc]가 1인 곳이지만, game_board의 빈 칸은 0으로 표시돼있기 때문에 이를 반전시켜야 한다.
굳이 game_board의 모든 칸을 탐색해가며 빈칸을 찾을 필요가 없으니 먼저 game_board에 있는 빈 칸 리스트를 만들어야 한다. 이를 위한 visitedGameBoard를 만들고, List<List<Point>> 타입의 gameBoardLists를 만든다. 마찬가지로 table에 있는 퍼즐 조각을 위해 visitedTable과 tableLists를 만든다. game_board와 table에 있는 모든 조각들에 대해 bfs 메서드를 실행하여 나온 리스트를 각각의 lists에 삽입하고, tableLists에 있는 퍼즐 조각들은 회전할 수 있으니 각각 회전한 퍼즐 조각들을 저장할 List<Point>[][] 타입의 rotations를 만들어 각각 회전시켜 저장한다.
여기서 좀 헤맸는데, 이렇게 회전시킨 퍼즐 조각들을 game_board의 빈칸들과 비교할 때 문제가 생길 수 있다. 각각 처음 bfs 메서드를 실행한 좌표가 다르기 때문에 기준점이 달라질 수 있다는 것이다. 이렇게 기준점이 달라진다면 같은 모양의 조각이더라도 같다고 판단을 못 할 수 있다. 그 예시는 아래와 같다.
모든 조각은 왼쪽 상단에서부터 시작해서 bfs 메서드를 거치기 때문에 초기값은 모두 맨 왼쪽 상단에 있는 좌표가 기준이 된다. 하지만 퍼즐 조각이 회전을 하게 된다면 위와 같이 문제가 생긴다.
이를 해결하기 위한 조각 정규화가 필요하다. 회전한 이후의 퍼즐 조각의 가장 왼쪽 상단에 있는 좌표를 시작 좌표로 하기 위해 Point 클래스에서 compareTo(T o) 메서드를 다음과 같이 오버라이딩한다.
@Override
public int compareTo(Point o) {
if (this.r == o.r) {
return this.c - o.c;
} else {
return this.r - o.r;
}
}normalize 메서드는 각각의 조각을 나타내는 list를 collections.sort로 정렬한다. 이렇게 되면 list의 맨 앞에 있는 좌표가 조각의 맨 왼쪽 상단 좌표이며, 이 좌표를 base라고 할 때 base를 (0, 0)으로 만들기 위해 list에 있는 모든 좌표들에 대해 base의 좌표만큼 빼준다.
그러면 모든 회전된 퍼즐 조각들을 저장한 rotations 배열에 있는 모든 조각들에 대해 정규화를 실행하고, gameBoardLists에 있는 빈 칸 리스트들과 비교하여 채울 수 있는 모든 퍼즐 조각들을 채운다.
코드
import java.util.*;
class Point implements Comparable<Point> {
private int r, c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
public int getR() {
return r;
}
public int getC() {
return c;
}
@Override
public int compareTo(Point o) {
if (this.r == o.r) {
return this.c - o.c;
} else {
return this.r - o.r;
}
}
}
class Solution {
public List<Point> bfs(int[][] boardTable, boolean[][] visited, int r, int c) {
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(r, c));
List<Point> list = new ArrayList<>();
list.add(new Point(0, 0));
int n = boardTable.length;
int[] dr = {1, 0, -1, 0}, dc = {0, -1, 0, 1};
while (!queue.isEmpty()) {
Point p = queue.poll();
for (int i = 0; i < 4; i++) {
int nr = p.getR() + dr[i], nc = p.getC() + dc[i];
if (0 <= nr && nr < n && 0 <= nc && nc < n) {
if (!visited[nr][nc] && boardTable[nr][nc] == 1) {
visited[nr][nc] = true;
queue.offer(new Point(nr, nc));
list.add(new Point(nr - r, nc - c));
}
}
}
}
return list;
}
public List<Point> normalize(List<Point> list) {
Collections.sort(list);
Point base = list.get(0);
List<Point> normalized = new ArrayList<>();
for (Point p : list) {
normalized.add(new Point(p.getR() - base.getR(), p.getC() - base.getC()));
}
return normalized;
}
public int solution(int[][] game_board, int[][] table) {
int n = table.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
game_board[i][j] = game_board[i][j] == 1 ? 0 : 1;
}
}
List<List<Point>> tableLists = new ArrayList<>();
boolean[][] visitedTable = new boolean[n][n];
List<List<Point>> gameBoardLists = new ArrayList<>();
boolean[][] visitedGameBoard = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visitedTable[i][j] && table[i][j] == 1) {
visitedTable[i][j] = true;
tableLists.add(bfs(table, visitedTable, i, j));
}
if (!visitedGameBoard[i][j] && game_board[i][j] == 1) {
visitedGameBoard[i][j] = true;
gameBoardLists.add(bfs(game_board, visitedGameBoard, i, j));
}
}
}
int tableSize = tableLists.size();
List<Point>[][] rotations = new List[tableSize][4];
for (int i = 0; i < tableSize; i++) {
List<Point> tableList = tableLists.get(i);
for (int j = 0; j < 4; j++) {
rotations[i][j] = new ArrayList<>();
List<Point> rotatedList = rotations[i][j];
for (Point p : tableList) {
int rotatedR = j == 0 ? p.getR() : j == 1 ? -p.getC() : j == 2 ? -p.getR() : p.getC();
int rotatedC = j == 0 ? p.getC() : j == 1 ? p.getR() : j == 2 ? -p.getC() : -p.getR();
rotatedList.add(new Point(rotatedR, rotatedC));
}
rotations[i][j] = normalize(rotatedList);
}
}
int answer = 0;
boolean[] visited = new boolean[tableSize];
for (List<Point> gameBoardList : gameBoardLists) {
int maxSize = 0, maxIndex = -1;
for (int i = 0; i < tableSize; i++) {
List<Point> tableList = tableLists.get(i);
if (visited[i]) continue;
if (gameBoardList.size() == tableList.size()) {
for (int k = 0; k < 4; k++) {
boolean isValid = true;
List<Point> rotatedTableList = rotations[i][k];
for (Point p : rotatedTableList) {
boolean flag = false;
for (Point q : gameBoardList) {
if (p.getR() == q.getR() && p.getC() == q.getC()) {
flag = true;
break;
}
}
if (!flag) {
isValid = false;
break;
}
}
if (isValid) {
if (maxSize < tableList.size()) {
maxSize = tableList.size();
maxIndex = i;
}
}
}
}
}
if (maxIndex != -1) {
answer += maxSize;
visited[maxIndex] = true;
}
}
return answer;
}
}결론
DFS와 BFS는 알고리즘 중 내가 가장 자신 있어 했던 분야였다. 하지만 아이템 줍기 문제를 보고 나중에 실전에서 이런 생각을 할 수 있을까 하는 걱정이 생겼다. 또한 퍼즐 조각 채우기 문제는 그렇게 어려워 보이지 않았는데 퍼즐 조각 정규화에서 막혀서 결국 해결했을 때 환호성을 질렀던 기억이 있다.
이렇듯 아무리 자신 있는 분야라도 그 세계는 무궁무진하며, 언제든 나를 당황시킬 수 있으니 긴장의 끈을 놓지 말아야겠다는 생각이 들었다.
그리고 이 파트가 왜 DP보다 뒤에 있을까? 아무리 그래도 DP가 훨씬 더 어려웠던 것 같은데..
'프로그래머스 > 코딩테스트 고득점 Kit' 카테고리의 다른 글
| 프로그래머스 코딩테스트 고득점 Kit - 그래프(가장 먼 노드, 순위, 방의 개수) (3) | 2024.12.30 |
|---|---|
| 프로그래머스 코딩테스트 고득점 Kit - 이분탐색(입국심사, 징검다리) (0) | 2024.12.29 |
| 프로그래머스 코딩테스트 고득점 Kit - 동적계획법(N으로 표현, 정수 삼각형, 등굣길, 사칙연산, 도둑질) (0) | 2024.12.25 |
| 프로그래머스 코딩테스트 고득점 Kit - 탐욕법(체육복, 조이스틱, 큰 수 만들기, 구명보트, 섬 연결하기, 단속카메라) (0) | 2024.12.24 |
| 프로그래머스 코딩테스트 고득점 Kit - 완전탐색(최소직사각형, 모의고사, 소수 찾기, 카펫, 피로도, 전력망을 둘로 나누기, 모음사전) (1) | 2024.12.21 |