개념 : dx, dy 테크닉
2차원 좌표(배열)에서 특정 좌표에서 위, 아래, 오른쪽, 왼쪽으로 이동한 좌표를 구할 때 쓰이는 4방향 탐색 방식을 `dx, dy 테크닉`이라 합니다.
dy, dx 는 2차원 배열에서 4방향 탐색을 하는 것입니다. 따라서 수학 2차원 좌표에서 y가 + 되는 방향이, 2차원 배열에서는 인덱스가 감소하는 방향이 됩니다.
이때 시계방향으로 탐색할지, 반시계 방향으로 탐색할지에 따라 dy[4]배열의 값의 순서와 dx[4] 배열의 값의 순서가 달라집니다.
Warmup : 방향에 맞춰 이동
https://www.codetree.ai/ko/trails/complete/curated-cards/intro-move-in-direction/description
방향에 맞춰 이동 설명 | 코드트리
방향에 맞춰 이동을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
#include<bits/stdc++.h>
using namespace std;
#define distance aaaa
char direction;
int n, distance, ny, nx, y, x;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int main() {
// 방향 , 거리
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
while(n--) {
cin >> direction >> distance;
if(direction== 'S') ny = y + distance * dy[0], nx = x + distance *dx[0];
else if(direction == 'E') ny = y + distance *dy[1], nx = x + distance *dx[1];
else if(direction == 'N') ny = y + distance *dy[2], nx = x + distance *dx[2];
else ny = y + distance *dy[3], nx = x + distance *dx[3];
y = ny, x = nx;
}
cout << x << " " << y << '\n';
return 0;
}해설코드
#include <iostream>
#define DIR_NUM 4
using namespace std;
int n, x, y;
// 동, 서, 남, 북 순으로 dx, dy를 정의합니다.
int dx[DIR_NUM] = {1, -1, 0, 0};
int dy[DIR_NUM] = {0, 0, -1, 1};
int main() {
// 입력
cin >> n;
// 움직이는 것을 진행합니다.
while(n--) {
char c_dir; int dist;
cin >> c_dir >> dist;
// 각 방향에 맞는 번호를 붙여줍니다.
int dir;
if(c_dir == 'E')
dir = 0;
else if(c_dir == 'W')
dir = 1;
else if(c_dir == 'S')
dir = 2;
else
dir = 3;
// 주어진 방향대로 dist 거리만큼 이동했을 경우의
// 위치를 구해줍니다.
x += dx[dir] * dist;
y += dy[dir] * dist;
}
cout << x << " " << y;
return 0;
}
개념 : 방향회전을 위한 dx, dy 정의 방법
방향이 dx, dy 배열의 인덱스이기 때문에 방향이 항상 양수를 갖도록해야한다.
Warmup : 문자에 따른 명령 2
내풀이
#include<bits/stdc++.h>
using namespace std;
const int dy[4] = {0, -1, 0, 1};
const int dx[4] = {1, 0, -1, 0};
int y, x, ny, nx, dir_num = 3;
string n;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
// 현재 방향이 북쪽인지가 중요한듯.
for(int i = 0; i < n.size(); i++) {
if(n[i] == 'L') dir_num = (dir_num + 3) % 4;
else if(n[i] == 'R') dir_num = (dir_num + 1) % 4;
else{
ny = y + dy[dir_num], nx = x + dx[dir_num]; // 이동
// cout << x << " : " << y << ", " << nx << " : " << ny << "\n";
y = ny, x = nx;
}
}
cout << x << " " << y << "\n";
return 0;
}
개념 : 격자에서의 dx dy
개념 : 조건에 따라 방향이 변하는 경우
https://www.codetree.ai/ko/trails/complete/curated-cards/intro-small-marble-movement/description
작은 구슬의 이동 설명 | 코드트리
작은 구슬의 이동을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
풀이 시간 : 30분
접근방법
#include<bits/stdc++.h>
using namespace std;
// 방향을 바꾸는데 1 만큼의 시간이 소요됨
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int n, t, y, x, ny, nx, r, c, dir_num;
char d;
// int arr[54][54];
int get_dir(char d) { // 방향을 주면 방향벡터 반환
if(d == 'D') return 2;
else if(d == 'U') return 0;
else if(d == 'R') return 1;
else if(d == 'L') return 3;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> t;
cin >> r >> c >> d; // t초 후 위치한 격자의 칸 행 번호 출력 마지막에 +1 해줘야함.
r--; c--;
y = r, x = c;
// t초마다 움직임을 변경
dir_num = get_dir(d);
while(t--) {
// 방향을 바꿔야하는 때인지 좌표이동을 해도 되는 때인지를 구분하자
ny = y + dy[dir_num]; nx = x + dx[dir_num];
if(ny < 0 || ny >= n || nx < 0 || nx >= n) {
// 격자 끝에 부딪히면 바꾼다.
dir_num = (dir_num + 2) % 4; continue;
}
y = ny; x = nx;
}
cout << y + 1 << " " << x + 1;
return 0;
}
해설코드
#include <iostream>
#include <string>
#define ASCII_NUM 128
#define DIR_NUM 4
using namespace std;
int n, t;
int x, y, dir;
int mapper[ASCII_NUM];
int dx[DIR_NUM] = {0, 1, -1, 0};
int dy[DIR_NUM] = {1, 0, 0, -1};
bool InRange(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n;
}
void Simulate() {
while(t--) {
int nx = x + dx[dir], ny = y + dy[dir];
// 범위 안에 들어온다면 그대로 진행합니다.
if(InRange(nx, ny)) {
x = nx, y = ny;
}
// 벽에 부딪힌다면, 방향을 바꿔줍니다.
else
dir = 3 - dir;
}
}
int main() {
// 입력
cin >> n >> t;
// 각 알파벳 별 방향 번호를 설정합니다.
mapper['R'] = 0;
mapper['D'] = 1;
mapper['U'] = 2;
mapper['L'] = 3;
char c_dir;
cin >> x >> y >> c_dir;
x--; y--; dir = mapper[c_dir];
Simulate();
cout << x + 1 << " " << y + 1;
return 0;
}
개념 : 빙빙돌며 숫자 적기
https://www.codetree.ai/ko/trails/complete/curated-cards/intro-snail-number-square/description
빙빙 돌며 숫자 사각형 채우기 설명 | 코드트리
빙빙 돌며 숫자 사각형 채우기을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
풀이시간 : 20분
접근방법
1. 숫자를 1씩 늘린 값을 2차원 배열에 시계방향으로 탐색하며 저장한다.
2. 2차원 배열을 2중 for문으로 탐색하지않고 2차원 배열에 저장될 숫자 범위를 오름차순으로 반복한다.
- 2중 for문으로 배열을 탐색하는 것(`for(int i = 0; i <n; i++) { for(int j = 0; j < m; j++) {}}`) 은 탐색 방향이 오른쪽(동쪽)으로만 탐색하는 것이기 때문에 동쪽 방향으로만 탐색하면 문제 조건인 `배열의 끝에 도달`하거나 `이미 방문한 곳`을 충족하지 못한다.
- `for(int i =1 ; i < n * m; i++)`으로 반복하면 2차원 배열에 값을 기록한다.
- `i <= n *m 등호가 들어가지 않는 이유`는 등호가 들어가면 i = n * m 일 때 arr[1][1] = 17이 저장되기 때문에 유효하지 않는 값이 저장되기 때문이다. 이는 앞서 다음 좌표(ny,nx) 기준으로 숫자를 기록하기 때문에 i = n * m = 16, a[1][1] = arr[2][1] + 1 = 16 + 1이 된다.
3. 다음 배열 원소(ny, nx)에 저장할 숫자는 현재 배열 원소(y,x) 값에 + 1한 값으로 저장한다.
dx, dy 테크닉 적용 방법
방향벡터 배열 dy[4], dx[4]는 위, 오른쪽, 아래, 왼쪽 순으로 가리킵니다. 문제에서 기본 방향은 오른쪽이었으니 현재 방향 인덱스를 의미하는 `dir_num = 1`로 설정합니다.
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
#include<bits/stdc++.h>
using namespace std;
int visited[104][104];
int arr[104][104];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int ny, nx, y, x, n, m, dir_num = 1;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m; // 행 열
// 1차원 탐색을 진행하면서 1을 늘려가야함.
arr[0][0] = 1; visited[0][0] = 1;
for(int i = 1; i < n * m; i++) {
ny = y + dy[dir_num];
nx = x + dx[dir_num];
if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]){
// 배열의 인덱스를 도달하거나 이미 방문한적이 있으면 방향을 바꾸고 다시 이동해야함.
dir_num = (dir_num + 1) % 4; // 방향 바꿔야할 곳
ny = y + dy[dir_num];
nx = x + dx[dir_num];
}
arr[ny][nx] = arr[y][x] + 1; visited[ny][nx] = 1;
y = ny; x = nx;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m ;j++) {
cout << arr[i][j] << ' ';
}
cout << '\n';
}
return 0;
}
해설코드
#include <iostream>
#define MAX_NUM 100
#define DIR_NUM 4
using namespace std;
int n, m;
int arr[MAX_NUM][MAX_NUM];
int dx[DIR_NUM] = {0, 1, 0, -1};
int dy[DIR_NUM] = {1, 0, -1, 0};
int curr_x, curr_y; // 시작은 (0, 0) 입니다.
int dir; // 0: 오른쪽, 1: 아래쪽, 2: 왼쪽, 3: 위쪽
bool InRange(int x, int y){
return 0 <= x && x < n && 0 <= y && y < m;
}
int main() {
// 입력:
cin >> n >> m;
// 처음 시작 위치에 초기값을 적습니다.
arr[curr_x][curr_y] = 1;
// n*m개의 숫자를 적어야 합니다.
for(int i = 2; i <= n * m; i++) { // 숫자 i를 어디에 적을지 결정합니다.
// 현재 방향 dir를 기준으로 그 다음 위치 값을 계산합니다.
int next_x = curr_x + dx[dir], next_y = curr_y + dy[dir];
// 더 이상 나아갈 수 없다면
// 시계방향으로 90'를 회전합니다.
if(!InRange(next_x, next_y) || arr[next_x][next_y] != 0)
dir = (dir + 1) % 4;
// 그 다음 위치로 이동한 다음 배열에 올바른 값을 채워넣습니다.
curr_x = curr_x + dx[dir]; curr_y = curr_y + dy[dir];
arr[curr_x][curr_y] = i;
}
// 출력:
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++)
cout << arr[i][j] << " ";
cout << endl;
}
return 0;
}
Challenge : 되돌아오기
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-come-back/description
되돌아오기 설명 | 코드트리
되돌아오기을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
풀이시간 : 10분
접근방법
- 배열을 선언할 필요 없이 방향 이동할 때 필요한 현재 방향을 의미하는 `dir_num 변수`를 조작하여 방향벡터 배열(dy, dx)을 이용해 위치를 이동합니다.
- 배열을 사용하지 않아도 되는 이유는 배열에 기록할 값이 필요 없기 때문입니다. 관성으로 배열을 선언한다면 메모리만 낭비됩니다.
- 입력받은 distance 만큼 한번에 이동하면 안됩니다. `ny = y + dy[dir_num] * distance` (X) 매초마다 처음 위치(0,0)으로 돌아왔는지 체크해야하기 때문입니다.
#include<bits/stdc++.h>
using namespace std;
#define distance aaaa
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
char direction;
int distance, n, y, x, dir_num, y_, x_, t, ny, nx, state;
int get_dir(char d) {
if(d == 'N') return 0;
else if(d == 'E') return 1;
else if(d == 'S') return 2;
else return 3;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
y_ = y; x_ = x;
while(n--) {
cin >> direction >> distance;
dir_num = get_dir(direction);
for(int i = 1; i <= distance; i++) {
t++;
ny = y_ + dy[dir_num]; nx = x_ + dx[dir_num];
if(ny == y && nx == x) {
state = true; break;
}
y_ = ny, x_ = nx;
}
if(state) break;
// 매초마다 원래 위치로 돌아오는지 체크해야됨 한번에 distance만큼 이동하면 안됨. 그 중간에 만날 수 있기 때문에
}
if( state) cout << t << '\n';
else cout << -1 << "\n";
return 0;
}
해설코드
#include <iostream>
#define DIR_NUM 4
using namespace std;
int n, x, y;
// 동, 서, 남, 북 순으로 dx, dy를 정의합니다.
int dx[DIR_NUM] = {1, -1, 0, 0};
int dy[DIR_NUM] = {0, 0, -1, 1};
// 답을 저장합니다.
int ans = -1;
// 지금까지 걸린 시간을 기록합니다.
int elapsed_time;
// dir 방향으로 dist 만큼 이동하는 함수입니다.
// 만약 시작지에 도달하면 true를 반환합니다.
bool Move(int dir, int dist) {
while(dist--) {
x += dx[dir];
y += dy[dir];
// 이동한 시간을 기록합니다.
elapsed_time++;
// 시작지로 다시 돌아오면,
// 답을 갱신해줍니다.
if(x == 0 && y == 0) {
ans = elapsed_time;
return true;
}
}
return false;
}
int main() {
// 입력
cin >> n;
// 움직이는 것을 진행합니다.
while(n--) {
char c_dir; int dist;
cin >> c_dir >> dist;
// 각 방향에 맞는 번호를 붙여줍니다.
int dir;
if(c_dir == 'E')
dir = 0;
else if(c_dir == 'W')
dir = 1;
else if(c_dir == 'S')
dir = 2;
else
dir = 3;
// 주어진 방향대로 dist 만큼 위치를 이동해봅니다.
bool done = Move(dir, dist);
// 시작 위치에 도달했다면, 종료합니다.
if(done)
break;
}
cout << ans;
return 0;
}
Challenge : 되돌아오기 2
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-come-back-2/description
되돌아오기 2 설명 | 코드트리
되돌아오기 2을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
풀이시간 : 15분
접근방법
#include <bits/stdc++.h>
using namespace std;
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
string input;
bool state ;
int y, x, t, ny, nx, dir_num;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> input;
for(int i = 0; i < (int)input.size(); i++) {
if(input[i] == 'L' ) dir_num = (dir_num + 3) % 4;
else if(input[i] == 'R') dir_num = (dir_num + 1) % 4;
else if(input[i] == 'F') { // 이동
ny = y + dy[dir_num]; nx = x + dx[dir_num];
}
t++;
if(ny == 0 && nx == 0) { cout << t << "\n"; state = true; break;}
y = ny; x = nx;
}
if(!state) cout << -1 << "\n";
return 0;
}
Challenge : 격자위의 편안한 상태
격자 위의 편안한 상태 설명 | 코드트리
격자 위의 편안한 상태을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내풀이
풀이시간 : 20분
접근방법 : 색칠할 좌표(r,c)를 m번 받을 때마다 해당 좌표 기준 4방향 탐색하며 색칠한 곳이 3개일 때만 카운트
#include<bits/stdc++.h>
using namespace std;
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0 , -1};
int arr[104][104];
int n, m, r, c, ny, nx;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
while(m--) {
cin >> r >> c ; // 행 열
r--; c--;
arr[r][c] = 1; // 색칠한다.
int cnt = 0;
for(int k = 0; k < 4; k++) {
ny = r + dy[k];
nx = c + dx[k];
if(ny < 0 || ny >= n || nx < 0 || nx > n) continue;
if(arr[ny][nx] == 1) cnt++;
}
if(cnt == 3) cout << 1 << "\n";
else cout << 0 << "\n";
}
return 0;
}
해설코드
#include <iostream>
#include <string>
#define MAX_N 100
#define DIR_NUM 4
using namespace std;
int n, m;
int arr[MAX_N][MAX_N];
int dx[DIR_NUM] = {0, 1, 0, -1};
int dy[DIR_NUM] = {1, 0, -1, 0};
bool InRange(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n;
}
int AdjacentCnt(int x, int y) {
int cnt = 0;
for(int i = 0; i < DIR_NUM; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(InRange(nx, ny) && arr[nx][ny] == 1)
cnt++;
}
return cnt;
}
int main() {
// 입력
cin >> n >> m;
for(int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--;
y--;
arr[x][y] = 1;
// 해당 칸을 탐색합니다.
if(AdjacentCnt(x, y) == 3)
cout << 1 << endl;
else
cout << 0 << endl;
}
return 0;
}
Challenge : 거울에 레이저 쏘기 2
거울에 레이저 쏘기 2 설명 | 코드트리
거울에 레이저 쏘기 2을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
Challenge : 빙빙 돌며 숫자 사각형 채우기 2
내풀이
풀이시간 : 20분
접근방법
이전 문제와 다르게 방향을 바꾸는 영역에서 ny, nx좌표를 바로 구하지 않았음. 대신 i를 차감하지 않아야 그 다음 좌표(ny,nx)로 이동할 수 있음
`빙빙돌며 숫자 사각형 채우기1` 코드 그대로 써도 정답이다. 회전 초깃값과 방향만 `dir_num = 2`, `(dir_num + 3) % 4`으로 수정하면 된다.
#include<bits/stdc++.h>
using namespace std;
int arr[104][104], visited[104][104];
int n, m , y, x, ny, nx, dir_num = 2;
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
arr[0][0] = 1, visited[0][0] = 1;
for(int i = 1; i < n * m; i++) {
ny = y + dy[dir_num];
nx = x + dx[dir_num];
if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]){
dir_num = (dir_num + 3) % 4; // 방향전환
i--; // 방향 전환할 때는 차감이 되지 않도록한다.
continue;
}
arr[ny][nx] = arr[y][x] + 1; visited[ny][nx] = 1;
y = ny; x = nx;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) cout << arr[i][j] << " ";
cout << '\n';
}
return 0;
}
'Algorithm' 카테고리의 다른 글
| [CodeTree] 5회차: 북마크로 틀린 문제, 삽질한 문제 복습하는 습관 만들기 (0) | 2026.06.07 |
|---|---|
| [CodeTree] Ch5.시뮬레이션 2 - 배열 기록 (0) | 2026.06.05 |
| [CodeTree] Ch5.시뮬레이션 2 - 최장 연속 부분 수열 (0) | 2026.06.01 |
| [CodeTree] 4회차: 코테 꾸준히 하고자 하는 습관을 지켜주는 환경 (feat. 학습 리마인더 알림톡) (0) | 2026.06.01 |
| [CodeTree] Ch4. 시뮬레이션1 - 사각형 칠하기 (0) | 2026.05.26 |