문제 설명
해당 문제는 말 그대로 에어컨의 모든 바람 이동 위치를 파악 후 해당 갯수를 구해는 구현문제였습니다.
다만 고려해야 할 몇가지가 있었는데,
- 에어컨은 여러개가 가능하다.
- 바람이 이동한 횟수를 count ❌, 바람이 지나가는 자리의 ⭕
- 에어컨, 물건이 있는 자리 모두 바람 ⭕
라는 것이였습니다.
위에 3가지 사항은 사실 문제 지문과 예시 그림만 봐도 파악이 가능했었기 때문에 로직만 잘 파악하고 있다면 비교적 쉽게 구현이 가능한 문제였습니다.
내가 풀었던 방식
public class Main {
// 방향을 2차원 배열로 생성
static int[][] dirs =
{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// y, x값을 입력받는 내부 class 생성
static class Node {
int y, x;
Node(int y, int x) {
this.y = y;
this.x = x;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =
new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
// 에어컨을 저장할 List 생성 -> 여러개 에어컨 가능!
List<Node> airController = new ArrayList<>();
// 자리들을 저장하는 2차원 배열
int[][] arr = new int[row][col];
// 자리 input 및 에어컨을 List에 저장
for (int i = 0; i < row; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
int value = Integer.parseInt(st.nextToken());
arr[i][j] = value;
if (value == 9) {
airController.add(new Node(i, j));
}
}
}
// 접근했던 방향 판단용 3차원 boolean 배열 생성
boolean[][][] v = new boolean[row][col][4];
int result = 0;
// 에어컨 별 bfs 실행
for (Node air : airController) {
bfs(arr, v, air.y, air.x, row, col);
}
// 3차원 배열을 통해 count
for (boolean[][] vv : v) {
next:
for (boolean[] vvv : vv) {
for (boolean vvvv : vvv) {
if (vvvv) {
result++;
continue next;
}
}
}
}
//출력
System.out.println(result);
}
static void bfs(int[][] arr, boolean[][][] v, int preY, int preX, int row, int col) {
// queue 생성 및 초기 세팅
// 4방향으로 이동 가능하니, 0 ~ 3까지 입력
ArrayDeque<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < 4; i++) {
queue.offer(new int[]{preY, preX, i});
v[preY][preX][i] = true;
}
// queue가 비일 때까지 실행
while (!queue.isEmpty()) {
int[] qr = queue.poll();
int d = qr[2];
int ny = qr[0] + dirs[d][0];
int nx = qr[1] + dirs[d][1];
// 배열 내에서 움직일 때
if (ny >= 0 && ny < row && nx >= 0 && nx < col) {
// 방향 변환 메소드
int nd = changeDir(arr, ny, nx, d);
// 이미 왔던 방향이면 continue
if (v[ny][nx][nd]) {
continue;
}
// queue에 input, 방문여부 true
queue.add(new int[]{ny, nx, nd});
v[ny][nx][nd] = true;
}
}
}
// 방향전환 메서드
static int changeDir(int[][] arr, int y, int x, int d) {
if (arr[y][x] == 0) {
return d;
}
switch (arr[y][x]) {
case 1:
if (d == 0) {
d = 2;
} else if (d == 2) {
d = 0;
}
break;
case 2:
if (d == 3) {
d = 1;
} else if (d == 1) {
d = 3;
}
break;
case 3:
if (d == 0) {
d = 3;
} else if (d == 1) {
d = 2;
} else if (d == 2) {
d = 1;
} else if (d == 3) {
d = 0;
}
break;
case 4:
if (d == 0) {
d = 1;
} else if (d == 1) {
d = 0;
} else if (d == 2) {
d = 3;
} else if (d == 3) {
d = 2;
}
break;
}
return d;
}
}
문제점
- switch문 같은 조건문 사용을 통해 일일히 방향전환 진행
- 3차원 boolean 배열 사용으로 비효율적인 메모리 사용
다른 사람들의 방식
- 조건문 대신 방향전환용 2차원 배열 사용
static int[][] convert = { { 0, 0, 2, 1, 3 }, { 0, 3, 1, 0, 2 }, { 0, 2, 0, 3, 1 }, { 0, 1, 3, 2, 0 } };- 3차원 boolean 배열 대신 2차원 Byte배열 + 비트마스킹을 통한 visited 파악
// 4방향 각각 방문
boolean[][][] v = new boolean[row][col][4];
// 각 칸마다 4비트를 사용 (0000 ~ 1111)
byte[][] v = new byte[row][col]; 수정 후 코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static int[][] turns =
{ { 0, 2, 0, 3, 1 },
{ 1, 1, 3, 2, 0 },
{ 2, 0, 2, 1, 3 },
{ 3, 3, 1, 0, 2 } };
static class Node {
int y, x;
Node(int y, int x) {
this.y = y;
this.x = x;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =
new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
List<Node> airController = new ArrayList<>();
int[][] arr = new int[row][col];
for (int i = 0; i < row; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
int value = Integer.parseInt(st.nextToken());
arr[i][j] = value;
if (value == 9) {
airController.add(new Node(i, j));
}
}
}
byte[][] v = new byte[row][col];
int result = 0;
for (Node air : airController) {
bfs(arr, v, air.y, air.x, row, col);
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (v[i][j] != 0) result++;
}
}
System.out.println(result);
}
static void bfs(int[][] arr, byte[][] v, int preY, int preX, int row, int col) {
ArrayDeque<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < 4; i++) {
queue.offer(new int[]{preY, preX, i});
v[preY][preX] |= (1 << i);
}
while (!queue.isEmpty()) {
int[] qr = queue.poll();
int d = qr[2];
int ny = qr[0] + dirs[d][0];
int nx = qr[1] + dirs[d][1];
if (ny >= 0 && ny < row && nx >= 0 && nx < col) {
if(arr[ny][nx] == 9) {
continue;
}
int nd = turns[d][arr[ny][nx]];
if ((v[ny][nx] & (1 << nd)) != 0) {
continue;
}
queue.add(new int[]{ny, nx, nd});
v[ny][nx] |= (1 << nd);
}
}
}
}
느낀 점
- 그 동안 boolean배열을 습관적으로 사용해왔는데, 비트마스킹의 속도와 메모리 절약을 보고 앞으로는 비트마스킹을 더 적극적으로 사용해야 겠다는 생각이 들어습니다.
- Index를 통한 방향전환은 조건문이 아닌 다른 방식으로 풀 수 있다는 생각의 전환방식을 알게 되었습니다.
Backend Developer