배열 돌리기 4
아이디어 및 구현방법
-
회전 연산의 순서에 따라 최종 배열이 달라진다 했으므로 모든 경우의 수를 따져야함
- 순열 이용
- 순서에 상관있으므로
- 순열 이용
-
회전
- Direct 리스트를 이용하여 방향 전환 정보 설정
- direct 리스트의 방향 정보를 이용하여 인덱스를 옮겨가면서 값을 이동시킴
- 새로 저장 될 곳의 값을 임시 변수에 저장 (temp2)
- 이동시켜야할 곳의 값을 새로 저장될 곳으로 옮김 (temp1 -> 새로운 곳)
- 다음 연산시에 temp2에는 새로운 곳의 값을 저장해야 하므로 값이 덮어 씌워지는 오류 발생
- 이를 해결하기 위해 temp1 을 만들어 주고 값 이동이 끝나면 temp2의 값을 temp1에 미리 옮겨놓음
-
최솟값 찾음
-
새로운 경우의 수를 시작하기 전에 원본을 다시 가져와야함 (copy 함수)
시행 착오
- 순열에 있는 경우의 수를 찾는데 이전 경우에서 원본 데이터를 훼손했는데 이를 그대로 이용하여 틀렸음
- 임시 리스트를 만들어서 원본 데이터를 저장
코드
- python
def permutation(index):
if index == K:
temp = a[:]
perm.append(temp)
return
else:
in_perm = [False]*K
for i in range(index):
in_perm[a[i]] = True
c = [0]*K
cnt = 0
for i in range(K):
if not in_perm[i]:
c[cnt] = i
cnt += 1
for i in range(cnt):
a[index] = c[i]
permutation(index+1)
def count():
global min
for i in range(N):
sum = 0
for j in range(M):
sum += matrix[i][j]
if sum > min:
break
if sum < min:
min = sum
def copy(o,n):
for i in range(N):
for j in range(M):
n[i][j] = o[i][j]
return n
direct = [(0,1),(1,0),(0,-1),(-1,0)]
N,M,K = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(N)]
rotation = [list(map(int,input().split())) for _ in range(K)]
temp_matrix = [[0]*M for _ in range(N)]
perm = []
a = [0]*K
permutation(0)
min = 9876543210
temp_matrix = copy(matrix,temp_matrix)
for idx in range(len(perm)):
for i in range(K):
r,c,s = rotation[perm[idx][i]][0]-1,rotation[perm[idx][i]][1]-1,rotation[perm[idx][i]][2]
visited = [[False]*M for _ in range(N)]
for j in range(1,s+1):
dir = 0
y,x = r-j,c-j
ny,nx = y+direct[dir][0],x+direct[dir][1]
temp1 = matrix[y][x]
while not visited[ny][nx]:
temp2 = matrix[ny][nx]
matrix[ny][nx] = temp1
temp1 = temp2
y,x = ny,nx
visited[y][x] = 1
if (y,x) == (r-j,c-j) or (y,x) == (r-j,c+j) or (y,x) == (r+j,c-j) or (y,x) == (r+j,c+j):
dir = (dir+1)%4
ny,nx = y+direct[dir][0],x+direct[dir][1]
count()
matrix = copy(temp_matrix,matrix)
print(min)- java
import java.io.*;
import java.util.*;
public class Main17406_배열돌리기4 {
static int N, M, K;
static int[][] matrix;
static int[][] tempMatrix;
static int[][] rotation;
static int[][] direct = {
{0,1},
{1,0},
{0,-1},
{-1,0},
};
static boolean[][] visited;
static int[][] perm;
static int[] a;
static int top = 0;
static int min = 987654321;
public static void permutation(int index, int[] a) {
int i,j,cnt;
if (index == K) {
for (i=0; i<K; i++) {
perm[top][i] = a[i];
}
top ++;
} else {
boolean[] inPerm = new boolean[K];
for (i=0; i<index; i++) {
inPerm[a[i]] = true;
}
int[] c = new int[K];
cnt = 0;
for (i=0; i<K; i++) {
if (!inPerm[i]) {
c[cnt] = i;
cnt ++;
}
}
for (i=0; i<cnt; i++) {
a[index] = c[i];
permutation(index+1, a);
}
}
}
public static int[][] copy(int[][] o, int[][] n) {
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
n[i][j] = o[i][j];
}
}
return n;
}
public static void count() {
int sum;
for (int i=0; i<N; i++) {
sum = 0;
for (int j=0; j<M; j++) {
sum += matrix[i][j];
if (sum > min) {
break;
}
}
if (sum < min) {
min = sum;
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int i,j,r,c,s;
int dir,y,x,ny,nx;
int temp1,temp2;
matrix = new int[N][M];
tempMatrix = new int[N][M];
for (i=0; i<N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (j=0; j<M; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
rotation = new int[K][3];
for (i=0; i<K; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (j=0; j<3; j++) {
rotation[i][j] = Integer.parseInt(st.nextToken());
}
}
a = new int[K];
perm = new int[720][K];
permutation(0, a);
tempMatrix = copy(matrix,tempMatrix);
for (i=0; i<top; i++) {
for (j=0; j<K; j++) {
visited = new boolean[N][M];
r = rotation[perm[i][j]][0]-1;
c = rotation[perm[i][j]][1]-1;
s = rotation[perm[i][j]][2];
for (int idx=1; idx<=s; idx++) {
dir = 0;
y = r-idx;
x = c-idx;
ny = y + direct[dir][0];
nx = x + direct[dir][1];
temp1 = matrix[y][x];
while (!visited[ny][nx]) {
temp2 = matrix[ny][nx];
matrix[ny][nx] = temp1;
temp1 = temp2;
y = ny;
x = nx;
visited[y][x] = true;
if ((y==r-idx && x==c-idx) || (y==r-idx && x==c+idx) || (y==r+idx && x==c-idx) || (y==r+idx && x==c+idx)) {
dir = (dir+1) % 4;
}
ny = y + direct[dir][0];
nx = x + direct[dir][1];
}
}
}
count();
matrix = copy(tempMatrix, matrix);
}
System.out.println(min);
}
}
- Java queue
import java.io.*;
import java.util.*;
public class Main {
static int N, M, K;
static int[][] matrix;
static int[][] tempMatrix;
static int[][] rotation;
static int[][] direct = {
{0,1},
{1,0},
{0,-1},
{-1,0},
};
static boolean[][] visited;
static int[] a;
static int top = 0;
static int min = 987654321;
static Queue<int[] > q = new LinkedList<>();
public static void permutation(int index, int[] a) {
int i, j, cnt;
if (index == K) {
int[] temp = new int[K];
for (i=0; i<K; i++) {
temp[i] = a[i];
}
q.offer(temp);
top ++;
} else {
boolean[] inPerm = new boolean[K];
for (i=0; i<index; i++) {
inPerm[a[i]] = true;
}
int[] c = new int[K];
cnt = 0;
for (i=0; i<K; i++) {
if (!inPerm[i]) {
c[cnt] = i;
cnt ++;
}
}
for (i=0; i<cnt; i++) {
a[index] = c[i];
permutation(index+1, a);
}
}
}
public static int[][] copy(int[][] o, int[][] n) {
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
n[i][j] = o[i][j];
}
}
return n;
}
public static void count() {
int sum;
for (int i=0; i<N; i++) {
sum = 0;
for (int j=0; j<M; j++) {
sum += matrix[i][j];
if (sum > min) {
break;
}
}
if (sum < min) {
min = sum;
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int i, j, r, c, s;
int dir, y, x, ny, nx;
int temp1, temp2;
matrix = new int[N][M];
tempMatrix = new int[N][M];
for (i=0; i<N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (j=0; j<M; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
rotation = new int[K][3];
for (i=0; i<K; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (j=0; j<3; j++) {
rotation[i][j] = Integer.parseInt(st.nextToken());
}
}
a = new int[K];
permutation(0, a);
tempMatrix = copy(matrix,tempMatrix);
while (!q.isEmpty()) {
int[] perm = q.poll();
for (j=0; j<K; j++) {
visited = new boolean[N][M];
r = rotation[perm[j]][0]-1;
c = rotation[perm[j]][1]-1;
s = rotation[perm[j]][2];
for (int idx=1; idx<=s; idx++) {
dir = 0;
y = r - idx;
x = c - idx;
ny = y + direct[dir][0];
nx = x + direct[dir][1];
temp1 = matrix[y][x];
while (!visited[ny][nx]) {
temp2 = matrix[ny][nx];
matrix[ny][nx] = temp1;
temp1 = temp2;
y = ny;
x = nx;
visited[y][x] = true;
if ((y==r-idx && x==c-idx) || (y==r-idx && x==c+idx) || (y==r+idx && x==c-idx) || (y==r+idx && x==c+idx)) {
dir = (dir+1) % 4;
}
ny = y + direct[dir][0];
nx = x + direct[dir][1];
}
}
}
count();
matrix = copy(tempMatrix, matrix);
}
System.out.println(min);
}
}
웹뷰 개발에 관심 많은 Front-end 개발자입니다.