1.4 대표문제. Ladder
위의 문제를 푸는 방법은 다음과 같이 있을 수 있다.
- 전체 시작점을 순차적으로 끝 점에 도달하는 지 테스트를 해본다.
- X표시가 있는 끝점에서 거꾸로 시작지점으로 도달하는 테스트를 해본다.
최적의 방법은 2번이다.
2차원 배열이 필요하다.
사다리를 1로 표시하고, 사다리가 아닌 공간은 0으로 표시하자
손회를 할 때, 문제의 주어진 조건인 이동하는 중 왼쪽 사다리와 오른쪽 사다리를 만나면 이동하는 것을 포함시킨다. 먼저 문제를 해결하기 전에 배열의 순회에 대해서 알아보도록 하자.
1차원의 순회방식은 처음부터 끝까지, 끝부터 처음까지 순회하는 경우가 많다. 하지만 2차원 배열은 필요에 따라 여러 순회방식이 있다. 대표적인 경우가 네가지 이며
- 행 우선 순회
- 열 우선 순회
- 지그재그 순회
- 대각선 순회가 있다.
위 4개의 순회 성질을 적절히 사용하여 간단한 길 찾기 알고리즘을 짤 수도 있다.
이를 델타를 이용한 2차 배열 탐색이라고 부르기도 하는데 기준 순회는 일정한 규칙을 가지고 지속적으로 순회 했따면, 이 탐색 법은 상황에 따라 탐색할 위치를 바꿔가며 탐색해가는 방법이다.
int ary[n][n];
int dx ={0,0,-1,1};//상하좌우
int dy ={-1,1,0,0};
for(int i =0;i < n ;i++){
for(intj =0;j <n ;j++){
for(k =0;k <4;k++){inttestX =i +dx[k];
int testY =j + dy[k];
test(ary[testY][testX]);
}
}
}
X의 변화량과 Y의 변화량을 저장해두었다 상황에 따라 배열의 index값을 적절히 변화시키는 형태이다.
그럼 이제 위와 같은 순회와 탐색을 통해 아래의 문제를 해결해보자.
연습 문제. 절대값의 합 구하기
5x5의 2차 배열에 무작위로 25개의 숫자로 쵝화 한 후 25개의 요소에 대해서 그 요소와 이웃한 요소와의 차의 절대값을 구한 뒤, 구한 모든 값의 총합을 구한다.
본 문제는 행이나 열 우선 순회를 돌면서 상하좌우에 있는 값과 비교하는 과정을 거치면 쉽게 해결할 수 있다. 앞서 순회에 대한 내용을 충분히 배웠으니 바로 프로그램을 작성해보자.
import java.util.Scanner;
public class Solution {
static int n = 5;
// 할당된 배열을 넘어가지 않도록 한다.
public static boolean isWall(int x, int y)
{
if(x<0 || x>=5) return true;
if(y<0 || y>=5) return true;
return false;
}
//절대값을 구한다.
static int calAbs(int a1, int a2)
{
return (a1-a2) > 0 ? (a1-a2) : -(a2-a2);
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
int [][]arr =
{
{9,20,2,18,11},
{19,1,25,3,21},
{8,24,10,17,7},
{15,4,16,5,6},
{12,13,22,23,14}
};
int[] dx = {0,0,-1,-1}; // 상하좌우
int[] dy = {-1,1,0,0}; //
int newX, newY;
int sum = 0;
//좌표 축을 어떻게 정하느냐에 따라서 행이나 열 우선순회가 된다.
for(int y = 0 ; y < n; y++)
{
for(int x = 0; x< n; x++)
{
for(int dir = 0 ; dir < 4; dir++)
{
newX = x + dx[dir];
newY = y + dy[dir];
if(!isWall(newX,newY)) sum += calAbs(arr[y][x],arr[newX][newY]);
}
}
}
System.out.printf("sum = %d\n", sum);
}
}
연습문제. 2차원 배열 정렬
본 문제의 경우 달팽이의 등껍질처럼 배열을 순회 해야하는 것이 조금 복잡하기 때문에 버블이나 카운팅 정렬과는 다른 방법을 고안해야 한다.
선택정렬
정렬 과정
- 주어진 리스트 중에서 최소값을 찾는다.
- 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
- 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.
선택 정렬을 이용하여 다음과 같이 문제를 해결할 수 있다.
해결하려고 했는데 java.lang.ArrayIndexOutOfBoundsException: 0 이 에러가 계속 뜬다. array인덱스에 -1이 들어갔다는거다. 이 코드가 이해가 잘 안가므로. 수정해야 한다.
public class Solution {
static int n = 5;
// 할당된 배열을 넘어가지 않도록 한다.
// 배열에서 최소값을 찾는다.
public static int sel_min(int arr[][])
{
int min = 0 ;
int minX = 0;
int minY = 0;
min = arr[0][0];
//최소값을 찾기 위해서 굳이 달팽이처럼 찾을 필요는 없다.
for(int i = 0 ; i <5; i++)
for (int j = 0 ; j <5; j++)
if(min > arr[i][j])
{
min = arr[i][j];
minX = i;
minY = j;
}
arr[minX][minY]= 26; // 최소값을 중복해서 찾지 않기 위해 충분히 큰 값으로 바꿔놓는다.
return min;
}
public static void main(String[] args) {
int [][]arr = {
{9,20,2,18,11},
{19,1,25,3,21},
{8,24,10,17,7},
{15,4,16,5,6},
{12,13,22,23,14}
};
int [][]sorted_arr = {
};
int cur_min = -1;
int X, Y;
int newX = 0; int newY=0;
//배열을 순회할 때, 다음으로 이동할 방향을 정한다.
int dx[] = {1,0,-1,0}; // 상하좌우
int dy[] = {0,1,0,-1};
int dir_stat = 0 ;
for(int i = 0; i< 25; i++)
{
cur_min = sel_min(arr);
X = newX;
Y = newY;
sorted_arr[Y][X] = cur_min;
newX = X + dx[dir_stat];
newY = Y + dy[dir_stat];
//경계면에서 방향을 바꾼다.
if(sorted_arr[newY][newX] != 0 || newY>4 || newX>4) {
dir_stat = (dir_stat+1)%4;
newX = X + dx[dir_stat];
newY = Y + dy[dir_stat];
}
}
for(int i = 0 ; i < 5; i++)
{
for(int j = 0 ; j < 5; j++)
System.out.println(sorted_arr[i][j]);
}
}
}
1.4 대표문제 Ladder 해결하기
도착점에서 거꾸로 올라가자.
100x100크기의 2차원 배열이면 충분하지만 경계면에서 처리를 쉽게하기 위해 아래 그림과 같이 여유 공간을 만든다.
이런 여유를 두지 않는다면 배열의 크기를 벗어난 부분을 조사하지 않도록 처리를 해주어야 한다. 메모리를 조금 아끼는 것 보다는 처리를 심플하게 하는 것이 중요하다. 이렇게 주어진 입력보다 조금 더 크게 배열을을 잡는 경우는 미로 찾기, 지뢰 찾기 등이 있다.
가장 먼저 해야할 일은 도착점을 찾는 것이다. 도착점을 찾는 이후에는 좌우에 길이 있는지 살펴보고 없다면 위로 간다. 이 작업만 반복해서 진행 하면된다.
import java.util.Scanner;
public class Solution {
static int n = 5;
// 할당된 배열을 넘어가지 않도록 한다.
// 배열에서 최소값을 찾는다.
public static int search(int Map[][], int start)
{
int y = 100 ; int x = start;
while(y != 1)
{
if(Map[y][x-1] == 1) // 좌측 사다리가 있으면
{
while(Map[y][x-1] != 0) {//끝까지 이동한 뒤
x--;
}
y--; // 위로 한칸 올라간다.
}
else if(Map[y][x+1] == 1) //우측 사다리가 있다면
{
while(Map[y][x+1] != 0)
{
x++;
}
y--; // 위로 한칸 올라간다.
}
else{
y--;
}// 좌우측에 사다리가 없는 경우 위로 한칸 이동한다.
}
return x;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
int i, j;
int target = 0;
for(int t = 0 ; t < 10; t++) {
int num = stdIn.nextInt();
//사다리 초기화
int [][]Map = new int[102][102];
for(i = 1; i<101; i++)
for(j = 1; j< 101; j++)
Map[i][j] = stdIn.nextInt();
// 도착 지점 찾기
for(i = 0 ; i< 102; i ++) {
if(Map[100][i] ==2) {
target = i;
break;
}
}
System.out.print("#"+num+ " ");
System.out.println(search(Map,target)-1);
}
}
}
참고자료
소프트웨어 아카데미 S/W Problem Solving
Self Study Book 1. 4차시 순열, 선택 정렬, 대표문제 -Ladder