안녕하세요.
오래만에 글을 씁니다.
코딩 테스트 준비 겸 다시금 삼성 모의 역량 테스트를 풀어봤습니다.
새로운 문제가 추가되어서 풀어보고 글을 남깁니다.
문제URL
전체 소스입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class pinball_5650 {
static int answer;
static int N;
static int[][] arr;
//상0 하1 좌2 우3
static int[][] pos = {{-1,0},{1,0},{0,-1},{0,1}};
static int[][] reflection = {
{},
//하,우,상,좌
{1,3,0,2},
//우,상,하,좌
{3,0,1,2},
//좌,상,우,하
{2,0,3,1},
//하,좌,우,상
{1,2,3,0},
//하,상,우,좌
{1,0,3,2}
};
static List<WormHole> holeList;
static class WormHole{
int row;
int col;
int id;
public WormHole(int row, int col, int id) {
super();
this.row = row;
this.col = col;
this.id = id;
}
@Override
public String toString() {
return row + " " + col + " " + id;
}
@Override
public boolean equals(Object obj) {
return this.toString().equals(obj.toString());
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new FileReader("test.txt"));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
answer = 0;
holeList = new ArrayList<WormHole>();
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if(arr[i][j] >= 6) {
holeList.add(new WormHole(i, j, arr[i][j]));
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(arr[i][j] == 0) {
for (int k = 0; k < pos.length; k++) {
go(i, j, k);
}
}
}
}
sb.append("#").append(tc).append(" ").append(answer).append("\n");
}
System.out.println(sb);
}
private static void go(int row, int col, int dir) {
int nr = row;
int nc = col;
int count = 0;
boolean gameOver = false;
while(!gameOver) {
nr += pos[dir][0];
nc += pos[dir][1];
if(posCheck(nr, nc)) {
if(row == nr && col == nc) {
gameOver = true;
break;
}
if(arr[nr][nc] >= 1 && arr[nr][nc] <= 5) {
count++;
dir = reflection[arr[nr][nc]][dir];
}else if(arr[nr][nc] >= 6 && arr[nr][nc] <= 10) {
WormHole pairHole = findPairHole(new WormHole(nr,nc,arr[nr][nc]));
nr = pairHole.row;
nc = pairHole.col;
}else if(arr[nr][nc] == -1) {
gameOver = true;
break;
}
}else {
count++;
dir = reverseDir(dir);
}
}
answer = Math.max(answer, count);
}
private static boolean posCheck(int row, int col) {
return row >= 0 && row < N && col >= 0 && col < N;
}
private static int reverseDir(int dir) {
return dir % 2 == 0 ? dir+1 : dir-1;
}
private static WormHole findPairHole(WormHole wormHole) {
for (WormHole item : holeList) {
if(wormHole.equals(item)) continue;
if(wormHole.id == item.id) {
return item;
}
}
return null;
}
}풀이에 대해서 말해보도록 하겠습니다.
먼저 이 문제는 공이 원점으로 돌아오거나 블랙홀에 도달하는 시점이 종료시점입니다.
공이 벽이나 블록에 부딧힐때마다 점수를 얻고 웜홀에는 점수를 얻지 않습니다.
이러한 형태로 맵이 주어지며 0번은 빈공간 1~5번은 벽 6~10번은 웜홀 -1은 블랙홀입니다.
문제에서 원하는 답은 어떤 빈공간에 어떤 방향으로 놓고 시작해야 가장 많은 점수를 얻는지입니다.
출력은 위치나 방향이 아닌 가장 큰 점수를 얻은 값을 출력하면 되기에 전부 해보면 된다는 결론이 나왔습니다.
코드를 보며 문제를 풀어가보겠습니다.
//상0 하1 좌2 우3
static int[][] pos = {{-1,0},{1,0},{0,-1},{0,1}};
static int[][] reflection = {
{},
//하,우,상,좌
{1,3,0,2},
//우,상,하,좌
{3,0,1,2},
//좌,상,우,하
{2,0,3,1},
//하,좌,우,상
{1,2,3,0},
//하,상,우,좌
{1,0,3,2}
};이 문제에서 가장 중요하다고 생각되는 변수입니다. 다른 접근 방법도 많이 있겠지만 저같은 경우 각각의 블록마다 오는 방향과 바뀌는 방향을 미리 정해두고 시작하면 수월하게 문제를 풀 수 있을 것이라고 생각되어 먼저 선언을 한 후 시작했습니다.
pos 변수의 경우 상 하 좌 우 순서로 x, y 좌표에 값을 더함으로 진행방향으로 움직이는 것을 표현하고자 선언했습니다.
예를 들어 0, 0에서 시작하고 진행방향은 아래라고 한다면 제가 정한 기준으로 아래는 1이기에 pos[1]을 참조해 pos[1][0]인 1은 x값에 더하고 pos[1][1]인 0은 y값에 더해 1,0으로 이동되는 것입니다.
다음으로 reflection변수는 지도상에 블록들이 1번부터 5번까지로 표시된다는 것을 참고하여 배열의 첫번째는 비워두고 1번부터 각 블록에 대해 상 하 좌 우로 진입했을 때 어디로 방향을 변경해야 하는지를 맵핑해두었습니다.
하나만 예를 들어보면 1번 블록에 왼쪽방향성을 가진 공이 진입했을 경우에는 위로 간다. 라는 것을 제 방향 기준 순서인 상하좌우에 맞춰 3번째 자리에 0을 넣어주었습니다.
다음으로 웜홀 리스트입니다.
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if(arr[i][j] >= 6) {
holeList.add(new WormHole(i, j, arr[i][j]));
}
}
}
지도를 입력받으면서 6번이상인 숫자를 발견하면 웜홀이기때문에 리스트를 하나 만들어두고 미리 저장을 해 두었습니다.
문제 설명상에 웜홀은 없을 수도 있고 있다면 반드시 쌍으로 존재한다는 문항이 있습니다.
각각의 웜홀을 키값 형식으로 해쉬맵에 등록을 해둘까 생각도 했지만 웜홀의 숫자가 적고 리스트로 순회해도 충분할 것이라고 생각해 리스트로 접근을 했습니다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(arr[i][j] == 0) {
for (int k = 0; k < pos.length; k++) {
go(i, j, k);
}
}
}
}다음으로 이제 가장 많은 점수를 얻는 공의 위치와 방향을 찾아야 하기때문에 세로, 가로, 방향의 순서로 반복문을 만들어주고 초기의 공을 놓을 수 있는 위치는 빈공간뿐이기에 0이 입력된 자리에만 상하좌우 방향 모두로 go 메소드를 실행시켜줍니다. 매개변수는 마찬가지로 세로, 가로, 방향입니다.
private static boolean posCheck(int row, int col) {
return row >= 0 && row < N && col >= 0 && col < N;
}
private static int reverseDir(int dir) {
return dir % 2 == 0 ? dir+1 : dir-1;
}
go 메소드를 설명하기 전에 사용한 메소드 2가지를 먼저 설명하겠습니다.
posCheck의 경우 배열의 index outbound 오류를 예방하기위해 매 이동시 벽에 도달했는지를 체크하기 위한 메소드입니다.
reverseDir 메소드는 문제상에 벽에 도달한 경우에도 방향을 반대로 바꿔 진행하기에 제가 정한 방향 순서 상하좌우 순서에 맞춰 2로 나눈 나머지가 0일 경우에는 0,2(상,좌) 1일 경우에는 1,3(하,우)이기에 각각 1을 더하고 빼주는 방법으로 방향을 반대로 리턴해주는 메소드입니다.
private static WormHole findPairHole(WormHole wormHole) {
for (WormHole item : holeList) {
if(wormHole.equals(item)) continue;
if(wormHole.id == item.id) {
return item;
}
}
return null;
}
static class WormHole{
int row;
int col;
int id;
public WormHole(int row, int col, int id) {
super();
this.row = row;
this.col = col;
this.id = id;
}
@Override
public String toString() {
return row + " " + col + " " + id;
}
@Override
public boolean equals(Object obj) {
return this.toString().equals(obj.toString());
}
}다음으로 웜홀을 만났을 때 사용할 메소드입니다. 웜홀은 각각 같은 고유번호를 가진 웜홀이 1개씩 더 존재하기에 사전에 미리 리스트에 담아둔 웜홀리스트를 참고하면 됩니다.
한가지 작업을 해두어야 할 문제가 있습니다. 리스트 내에는 현재 웜홀도 같이 들어있기 때문에 해당 웜홀을 제외한 웜홀 중 같은 고유번호를 가진 웜홀을 찾아야 하기때문에 row, col 좌표값이 다르면서 id가 같은 웜홀을 찾으면 되겠지만 저는 3가지를 계속 비교하는 수고를 줄이고자 toString 메소드와 equals 메소드를 오버라이딩해서 equals메소드로 해당 웜홀이 같은 웜홀인지를 참고하는 방식을 채택했습니다.
findPairHole 메소드를 호출해 반대편 웜홀을 찾습니다. 같은 자리의 웜홀의 경우 continue를 사용해 제외하도록 했습니다.
private static void go(int row, int col, int dir) {
int nr = row;
int nc = col;
int count = 0;
boolean gameOver = false;
while(!gameOver) {
nr += pos[dir][0];
nc += pos[dir][1];
if(posCheck(nr, nc)) {
if(row == nr && col == nc) {
gameOver = true;
break;
}
if(arr[nr][nc] >= 1 && arr[nr][nc] <= 5) {
count++;
dir = reflection[arr[nr][nc]][dir];
}else if(arr[nr][nc] >= 6 && arr[nr][nc] <= 10) {
WormHole pairHole = findPairHole(new WormHole(nr,nc,arr[nr][nc]));
nr = pairHole.row;
nc = pairHole.col;
}else if(arr[nr][nc] == -1) {
gameOver = true;
break;
}
}else {
count++;
dir = reverseDir(dir);
}
}
answer = Math.max(answer, count);
}마지막으로 go 메소드입니다.
초기값으로 넘어온 row, col 값을 새로운 변수에 복사합니다.
공이 다시 원점으로 돌아왔을 경우에도 게임이 끝나기에 원래 자리를 알고 있어야 합니다.
이제 게임이 종료될때까지 반복문을 돌며 공을 이동시킵니다.
새로운 좌표 변수에 기존에 정의해두었던 pos 배열에서 현재 지정한 방향값에 맞는 값을 계속 추가해나아갑니다.
벽에 도달하지 않았다면 2가지 체크를 합니다.
먼저 공이 제자리로 돌아오지 않았는지 만약 돌아왔다면 게임을 종료합니다.
다음으로 움직인 자리의 번호를 체크합니다. 블록인지 웜홀인지 블랙홀인지를 체크해서 각각 상황에 맞게 코드를 만들어줍니다.
블록일 경우 점수를 추가하고 방향을 기존에 만들어둔 블록별 방향변환 배열에서 진입 방향을 입력하면 변경될 방향을 알 수 있습니다.
웜홀일 경우 출구가 될 웜홀을 찾아주는 findPairHole을 호출한 후 찾아낸 웜홀의 좌표로 현재 좌표를 수정해줍니다.
웜홀로 이동한 경우 방향은 유지됩니다.
마지막으로 블랙홀인 경우 게임을 종료합니다.
gameOver 변수는 추후에 사용할 수 있을 것 같아 만들어두었지만 반복문 깊이가 1이라서 결국 사용하지 않았습니다. 지우셔도 무방할 것 같습니다.
다음으로 벽에 도달한 경우에는 점수를 추가하고 진행방향을 정반대로 바꿔주는 reverseDir을 호출합니다.
블랙홀 또는 제자리로 공이 돌아와 반복문이 종료된다면 Math.max 함수를 사용해 현재까지 나온 가장 큰 점수와 지금 만들어진 새로운 점수를 비교해 더 큰 점수로 답을 치환해줍니다.
모든 방향이 끝나면 answer 안에 가장 큰 점수가 담겨있어 문제를 해결할 수 있게 됩니다.
이상으로 문제 풀이를 종료하겠습니다.
저는 문제가 안풀릴 때 인터넷에서 다른 사람들의 풀이를 보며 실마리를 얻는 경우가 많았습니다.
최고의 답안은 아니지만 저도 누군가에게 도움이 되는 글을 써보자는 마음으로 글을 작성했습니다.
감사합니다.
'algorithm' 카테고리의 다른 글
| [알고리즘] 백준 청소년 상어 19236 문제 풀이 (0) | 2020.12.03 |
|---|---|
| 백준 20061번 모노미노도미노2 문제풀이 (0) | 2020.11.30 |
| 백준 18809번 Gaaaaaaaaaarden 문제 풀이 (0) | 2020.03.22 |
| 백준 16235번 나무재테크 문제 풀이 (0) | 2020.03.05 |