기본 문법
- 기본 문법은 1차원 배열과 유사하다.
dx, dy 테크닉
dx, dy 테크닉은 어떤 2차원 좌표에서 이동을 할 때 간단하게 사용할 수 있는 알고리즘 기법이다.
예를 들어, 아래 그림처럼 4*5로 된 격자에 빨간 점에서 상,하,좌,우 로 이동하려면 어떻게 해야 할까?
if-else 문을 써서 이동 시켜도 되겠지만, 더 간단한 방법이 있다.
#출발 지점 설정
startR = 0;
startC = 0;
# 이동 방향
dir_num = 0
# 방향을 저장하는 순서는 문제에 따라 사용자가 지정 (현재는 우, 상, 좌, 하로 이동)
# 0 1 2 3
dc = [1, 0, -1, 0]
dr = [0, -1, 0, 1]
# 조건에 따라 이동
nextR = startR + dr[dir_num];
nextC = startC + dc[dir_num];
예제 적용
0. 문제
5*4 격자에 다음과 같이 숫자를 적으려면 어떻게 적어야 할까?
1. 규칙 찾기
- 처음에는 우측으로 이동한다.
- 벽에 부딪히면 아래로 이동한다.
- 또 벽에 부딪히면 좌측으로 이동한다.
- 또 벽에 부딪히면 위쪽으로 이동한다.
- 또 벽에 부딪히면 다시 우측으로 이동한다.
- 또 벽에 부딪히면 다시 아래로 이동한다.
- 또 벽에 부딪히면 다시 좌측로 이동한다.
- 또 벽에 부딪히면 다시 위쪽로 이동한다.
... 반복반복
이때, 이미 작성된 곳은 더 이상 방문하지 않는다.
2. 구현
1) 상하좌우 이동 구현
현재 위치를 (r,c) 라고 할 때,
- 우측으로 이동하면 c를 1 더해주면 된다. (r, c+1)
- 아래로 이동하면 r을 1 더해주면 된다. (r+1, c)
- 좌측으로 이동하면 c를 1 빼주면 된다. (r, c-1)
- 위로 이동하면 r을 1 빼주면 된다. (r-1, c)
이 이동을 코드로 구현하면 아래와 같이 간단하게 구현할 수 있다.
- dr은 r의 이동량, dc는 c의 이동량이다.
- moveIdx는 이동하는 방향을 의미하는 Index 번호이다.
우측으로 이동할거면 moveIdx를 0으로 두고, nextR = curR + dr[ moveIdx]; nextC = curC + dc[moveIdx]; 을 하면 된다.
// 우 하 좌 상 순서 움직임 구현
int[] dr = {0,1,0,-1};
int[] dc = {1,0,-1,0};
int moveIdx = 0; // 0 : 우, 1 : 하, 2 : 좌, 3 : 상 으로 이동
2) 회전 조건
벽에 부딪히거나 그 다음 위치에 값이 이미 있는 경우에는 moveIdx에 1을 더해 이동하는 방향을 바꿔준다.
우리는 1.규칙 찾기 단계에서 우측 -> 아래 -> 좌측 -> 위쪽 으로 이동한다는 것을 발견하고 이동 구현할 때 이 순서대로 구현했었다.
1. 벽에 부딪힌다는 것은 배열의 범위 밖을 벗어난다는 의미이고,
2. 이미 있는 값이라는 것은 초기 배열 선언 시 모두 0이 저장이 되므로 0이 아닌 수가 있으면 이미 있는 값으로 판단하면 된다.
저 두 경우에는 moveIdx의 값에서 1을 더해서 다음 방향으로 이동하도록 한다.
그런데, moveIdx가 4가 되면 어떻게 될까? dr[4]와 dc[4]는 없으므로 오류가 발생할 것이다.
우측 -> 아래 -> 좌측 -> 위쪽 의 이동을 마치면 다시 우측부터 시작해야 한다.
이 문제를 해결하기 위해 아래 간단한 코드로 해결할 수 있다.
// 1안
moveIdx = ++moveIdx % 4;
// 2안
nextR = curR + dr[moveIdx%4];
지금까지 언급한 것을 모두 코드로 옮기면 아래와 같다.
import java.util.*;
class Solution
{
public static void main(String args[]) throws Exception
{
// input //
Scanner sc = new Scanner(System.in);
int T = Integer.parseInt(sc.nextLine());
for(int testCase=1; testCase<=T; testCase++) {
int N = Integer.parseInt(sc.nextLine());
// logic //
int[][] board = new int[N][N];
// 1) 우 하 좌 상 순서 움직임 구현
int[] dr = {0,1,0,-1};
int[] dc = {1,0,-1,0};
int moveIdx = 0; // 0 : 우, 1 : 하, 2 : 좌, 3 : 상 으로 이동
// 현재 위치
int curR = 0;
int curC = 0;
// 채울 번호
int fillNum = 2;
// 초기에는 무조건 0,0에 1을 채운다.
board[0][0] = 1;
while(fillNum <= N*N) {
// 1) 이동 구현
int nextR = curR + dr[moveIdx%4];
int nextC = curC + dc[moveIdx%4];
// 2) 벽에 닿을 조건(배열 범위 밖으로 가는 조건 예외 처리)
if(nextR < 0 || nextC < 0 || nextR >= N || nextC >= N) {
moveIdx++;
continue;
}
// 2) 이미 있는 값에 대한 예외 처리
if(board[nextR][nextC] != 0) {
moveIdx++;
continue;
}
board[nextR][nextC] = fillNum;
fillNum++;
curR = nextR;
curC = nextC;
}
// 정답 출력
System.out.println("#"+testCase);
for(int r=0; r<N; r++) {
for(int c=0; c<N; c++) {
System.out.print(board[r][c]+" ");
}
System.out.println();
}
} // tc
}
}
연습 문제
2차원 배열과 dx, dy 테크닉을 익히기 좋은 문제를 선별했다.
| 코드트리_대각선으로 숫자 채우기 | https://www.codetree.ai/missions/4/problems/diagonal-numbering/description | #2차원 배열 #dx,dy 테크닉 |
| 코드트리_격자 반대로 채우기 | https://www.codetree.ai/missions/4/problems/grid-anti-fill/description | #2차원 배열 #dx,dy 테크닉 |
| SWEA_1954. 달팽이 숫자 | https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE&problemTitle=달팽이&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 | #2차원 배열 #dx,dy 테크닉 |
