da9dac

문제

접근 방식

문제가 너무 대놓고 그래프로 네 방향을 탐색하라고 나와 있는데 이거에 낚이면 시간초과에 걸린다.

장애물이 없는 지도가 주어져서 현재 지점의 좌표와 이동하고자 하는 지점의 좌표의 차를 구하면

몇 칸을 이동해야하는지 알 수 있기 때문에 직접 한 칸씩 움직일 필요가 없다.

그래서 집의 좌표와 민초우유의 좌표만 구해두고 집의 위치에서부터 시작해서

현재 좌표와 민초우유의 좌표의 차를 구하고 현재 체력보다 작거나 같다면 이동해주면 된다.

풀이

public class Main {

	static int n, m, h, max = 0, milk = 0;
	static Pair home;
	static ArrayList<Pair> milks = new ArrayList<>();
	static boolean[] isVisited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				int x = Integer.parseInt(st.nextToken());

				if (x == 1) {
					home = new Pair(i, j);
				} else if (x == 2) {
					milks.add(new Pair(i, j));
					milk++;
				}
			}
		}

		isVisited = new boolean[milk];

		solve(home.x, home.y, 0);

		System.out.println(max);
	}

	static void solve(int x, int y, int eat) {
		for (int i = 0; i < milk; i++) {
			if (isVisited[i]) continue;

			isVisited[i] = true;

			Pair pair = milks.get(i);

			int nx = pair.x;
			int ny = pair.y;
			int distNext = getDist(x, y, nx, ny);

			if (distNext <= m) {
				m += h;
				m -= distNext;
				if (getDist(home.x, home.y, nx, ny) <= m) max = Math.max(max, eat + 1);
				solve(nx, ny, eat + 1);
				m -= h;
				m += distNext;
			}

			isVisited[i] = false;
		}
	}

	static int getDist(int ax, int ay, int bx, int by) {
		return Math.abs(ax - bx) + Math.abs(ay - by);
	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

문제

접근 방식

여러 풀이가 존재하는 문제 같지만 BFS를 사용해서 풀어봤다.

우선 문제에서는 10*10 맵이라고 했지만 그냥 100칸짜리 1차원 배열을 사용하는 것이

문제의 입력 양식을 처리하기가 편해서 맵과 방문 배열을 모두 1차원 배열을 사용했다.

평범한 BFS 문제와 방식은 비슷하지만 주사위의 눈만큼 이동하기 위해

방향 배열을 사용하는 것이 아닌 1 ~ 6까지 반복문을 돌아주었다.

사다리나 뱀은 무조건 타야 하기 때문에 이 부분만 주의하면서 탐색해 주고

방문 기록을 정수형 배열로 처리해 주사위를 굴린 횟수가 더 적은 경우에만

이동할 수 있게 해 주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int[] map = new int[101];
		int[] isVisited = new int[101];
		Arrays.fill(isVisited, -1);

		int nm = Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());

		while (nm-- > 0) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			map[x] = y;
		}

		Queue<Integer> q = new ArrayDeque<>();
		q.offer(1);
		isVisited[1] = 0;

		while (!q.isEmpty()) {
			int cur = q.poll();
			int move = isVisited[cur] + 1;

			for (int dice = 1; dice <= 6; dice++) {
				int next = cur + dice;

				if (next > 100) continue;

				if (map[next] != 0) {
					int x = map[next];

					if (isVisited[x] != -1 && isVisited[x] <= move) continue;

					isVisited[x] = move;
					q.offer(x);

					continue;
				}

				if (next == 100) {
					System.out.println(move);
					return;
				}

				if (isVisited[next] != -1 && isVisited[next] <= move) continue;

				isVisited[next] = move;
				q.offer(next);
			}
		}
	}
}

문제

접근 방식

바이토닉 수열인 오름차순, 내림차순, 오름차순 + 내림차순 수열 중 가장 긴 것을 찾아야 한다.

이전에 풀었던 문제 중 가장 긴 증가하는 부분 수열을 응용하면 풀 수 있는 문제인데

v		v			v	v	v
1	5	2	1	4	3	4	5	2	1

만약에 위와 같은 수열이 있다면 1, 2, 3, 4, 5가 가장 긴 증가하는 부분 수열일 것이고

	v			v	v			v	v
1	5	2	1	4	3	4	5	2	1

가장 긴 감소하는 부분 수열은 위와 같을 것이다.

가장 긴 증가하는 부분 수열과 감소하는 부분 수열의 길이를 표로 정리하면 다음과 같다.

1	5	2	1	4	3	4	5	2	1

1	2	2	1	3	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

이렇게 표를 정리하고 나면 같은 값에 해당하는 길이끼리 합치면

오름차순과 내림차순이 합쳐진 바이토닉 부분 수열을 만들 수 있는 것을 알 수 있다.

예를 들어 길이가 5인 증가하는 부분 수열과 3인 감소하는 부분 수열을 합치면

1, 2, 3, 4, 5 + 5, 2, 1 = 1, 2, 3, 4, 5, 5, 2, 1 만들어질 것이고

5는 겹치는 부분이니 총개수의 합인 8에서 1을 빼주면 된다.

정리하면 두 경우의 부분 수열의 길이를 구해서 합한 후에 가장 큰 값을 구해주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int max = 0;
		int[] arr = new int[n];
		int[] dp = new int[n];
		int[] dpr = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;

			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}

		for (int i = n - 1; i >= 0; i--) {
			dpr[i] = 1;

			for (int j = n - 1; j > i; j--) {
				if (arr[j] < arr[i]) {
					dpr[i] = Math.max(dpr[i], dpr[j] + 1);
				}
			}

			dp[i] += (dpr[i] - 1);
			max = Math.max(dp[i], max);
		}

		System.out.println(max);
	}
}

문제

접근 방식

노드 간의 거리가 모두 1로 동일할 때, 시작점 X에서 거리가 K인 정점을 출력해야 한다.

즉 탐색은 X에서 K번 까지의 이동만 진행해주면 되고, K번째 방문한 정점들을 모두 저장해주면 되는데

문제에서 요구하는 출력값이 정점의 번호를 오름차순으로 출력하는 것이기 때문에

트리셋이나 우선순위큐, 정렬 등을 사용해서 출력해주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());

		int[] isVisited = new int[n + 1];
		Arrays.fill(isVisited, -1);

		ArrayList<ArrayList<Integer>> near = new ArrayList<>();
		TreeSet<Integer> result = new TreeSet<>();

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			near.get(a).add(b);
		}

		Queue<Integer> q = new ArrayDeque<>();

		q.offer(x);
		isVisited[x] = 0;

		while (!q.isEmpty()) {
			int cur = q.poll();

			for (int next : near.get(cur)) {
				if (isVisited[next] != -1) continue;
				isVisited[next] = isVisited[cur] + 1;
				if (isVisited[next] == k) {
					result.add(next);
					continue;
				} else if (isVisited[next] > k) {
					continue;
				}
				q.offer(next);
			}
		}

		if (result.isEmpty()) {
			sb.append(-1);
		} else {
			for (int i : result) {
				sb.append(i).append("\n");
			}
		}

		System.out.println(sb);
	}
}

개요

 스프링을 처음 배우면 누구나 IoC와 DI에 대해서 학습을 하지만 작성자처럼 개발자가 개발에만 집중할 수 있게 하기 위해 객체의 생성과 관계 설정 같은 번거로운 작업들을 컨테이너에 떠넘기는 것 혹은 이와 비슷하게 개념적으로만 그런가 보다 하고 넘어가는 일들이 많은 거 같다. (아님 말고...)

 그래서 스터디에서 발표도 준비할 겸 토비의 스프링을 다시 정독하면서 DI가 무엇이고, 왜 필요한지, 적용함으로 얻을 수 있는 이득 등에 대해 최대한 간단하게 살펴보려 한다. (쓰다 보면 길어질 수도 있다)

객체 스스로 사용할 객체를 선택하고 생성하는 것이 맞을까?

 클라이언트의 주문에 대한 처리를 담당하는 주문 서비스 객체의 관심사는 무엇일까라고 생각하면 당연히 요청에 맞게 주문을 처리하는 것이다. 하지만 만약 객체 스스로 자신이 사용할 객체를 선택하고 생성한다면 이에 대한 관심사까지 담당하게 된다고 볼 수 있다.

 서로 다른 관심사끼리 응집되어 있다면 변경 시 서로의 변화에 영향을 받기 때문에 서로에게 영향을 주지 않기 위해 DI를 사용해 주문 서비스 객체의 핵심 관심사와 종류가 다른 관심사를 분리시킨다.

정적으로 의존 관계를 설정하면 왜 안 되는 걸까?

public class OrderService {

	private OrderRepository orderRepository = new OrderRepository();

}

public class OrderRepository {
	
}

 위의 경우는 DI를 적용하지 않았기 때문에 객체 스스로가 사용할 객체를 선택하고 생성하는 방식을 사용한다. 이미 엎드려 보고 물구나무서서 봐도 누구나 OrderService 객체가 OrderRepository 객체를 사용한다는 것을 알 수 있다.

 이런 정적인 의존 관계 설정 방식을 사용하면 설계와 코드 레벨에서 객체 간의 의존 관계가 직접적으로 드러나게 된다. 이게 왜 문제일까 생각해 보면 위에서 언급한 관심사의 분리 측면에서의 문제도 있지만, 클라이언트 객체(OrderService)가 자신이 사용할 서버 객체(OrderRepository)와 긴밀한 관계에 있게 되어 직접적으로 알고 있기 때문에 서버 객체의 변화에 따른 영향을 직접적으로 받게 된다.

동적으로 의존 관계가 설정된다면 어떨까?

 동적으로 의존 관계가 설정된다는 것은 설계나 코드 레벨에 객체 간의 실질적인 의존 관계가 직접적으로 드러나지 않고 런타임 시에 의존 관계가 설정되는 것이다. 이 부분도 설명만 들어서는 이해가 어려우니 코드로 살펴보겠다.

public class OrderService {

    private OrderRepository orderRepository;

    public OrderService(OrderRepository orderRepository) {
    	this.orderRepository = orderRepository;
    }
}

public interface OrderRepository {
	
}

public class OrderRepositoryA implements OrderRepository {
	
}

public class OrderRepositoryB implements OrderRepository {
	
}

 위의 코드만 보고 OrderService가 어떤 OrderRepository의 구현 클래스를 사용하는지 알 수 있을까?

 당연히 알 수가 없다. 필드와 생성자가 구현 클래스의 타입을 직접적으로 명시하지 않고 인터페이스를 타입으로 받고 있기 때문이다. 따라서 두 객체의 연관 관계는 설계나 코드 레벨에서는 OrderRepository의 구현 클래스 중 하나와 설정된다는 것만 알 수 있고, 런타임 시까지는 직접적인 연관 관계를 알 수 없다는 것이다.

그렇다면 외부로부터 주입받으면 무조건 DI일까?

public class OrderService {

    private OrderRepository orderRepository;

    public OrderService(OrderRepositoryA orderRepositoryA) {
    	this.orderRepository = orderRepositoryA;
    }
}

public interface OrderRepository {
	
}

public class OrderRepositoryA implements OrderRepository {
	
}

public class OrderRepositoryB implements OrderRepository {
	
}

 DI의 궁극적인 목표는 의존 관계를 런타임 시에 설정하는 것인데 위의 코드처럼 생성자의 파라미터에 OrderService 객체 스스로 자신이 주입받고 싶은 관계를 직접적으로 명시하고 있다면 DI라고 볼 수 없다.

 기존의 정적인 방식과 마찬가지로 설계와 코드 레벨에서 이미 OrderService 객체가 어떤 객체와 연관 관계를 맺을지 알 수 있기 때문이다. 하지만 DI를 의존성 주입이라는 관점에서만 바라본다면 외부로부터 의존성을 주입 받고 있긴 하니 DI라고 볼 수도 있다.

 그래도 DI의 가치를 생각해본다면 인터페이스를 활용해 런타임 시에 동적이 관계를 맺고 객체 간의 결합도를 낮추는 것이 객체지향적인 관점에서 더 좋다고 생각한다.

객체 간의 DI를 해주는 객체

 이쯤되면 런타임 시에 객체를 생성하고 객체들간의 의존 관계를 설정해주는 역할은 누가 수행하는지 궁금해질텐데, 이런 역할을 수행하는게 바로 많이 들어봤을 스프링 컨테이너다. 이번 글의 주제는 DI이기 때문에 컨테이너에 대해서는 나중에 자세히 다루고 지금은 넘어가겠다.

DI의 장점

 DI 자체가 지금까지 살펴봤듯이 객체지향 설계와 프로그래밍 원칙을 따른 기술이기 때문에 이들을 지켰을 때 얻을 수 있는 장점들을 자연스럽게 모두 얻을 수 있다고 보면 된다.

 관심사의 분리를 통해 응집도가 높은 코드를, 인터페이스를 통해 결합도가 낮은 코드를 작성할 수 있기 때문에 객체의 변경으로 인해 다른 객체에 발생하는 영향을 줄일 수 있고, 코드의 재사용성과 유연성, 유지보수성을 높일 수 있다.

 또한, 테스트 수행에 있어서도 대리 객체의 주입을 통해 손쉽게 외부 의존성을 대체하거나 특정 모듈이나 클래스를 고립시키고 테스트할 수 있다.

마치며

 정말 최대한 간략하게 정리하려 노력했지만 세상 일이란게 마음대로 되지 않는다. DI라는 개념 자체가 연관된 것들도 많고 워낙 복잡한 개념이다 보니 요점을 전달하면서 간략하게 적는다는게 참 쉽지 않다. 어쨋든 글을 작성하면서 개인적으로도 생각이 정리되다 보니 많은 도움이 되어 다행이다. (글을 읽는 사람들이 도움이 될진 모르겠지만...)

문제

접근 방식

m	v
1	65
2	98
2	95
5	99
5	96
5	90

보석의 무게와 가치를 위와 같이 무게가 가벼운 순으로, 같다면 가치가 높은 순으로 정렬한 후에

오름차순으로 정렬된 가방을 하나씩 보면서 현재 가방의 무게 이하인 보석을 모두 우선순위 큐에 넣고

가장 큰 값을 하나만 꺼내서 누적합에 더해주면 된다.

2
2
10
10

가방의 무게가 다음과 같을 때

[2]	98 95 65
[2]	95 65
[10]	99 96 90 65
[10]	96 90 65

처음 가방 무게가 2일 때는 98, 95, 65를 추가하고 그중에서 가장 큰 98을 큐에서 꺼내고

다음 가방 무게가 2일 때도 남은 95, 65 중에서 95를 꺼낸 후에

가방 무게가 10일 때 99와 90을 추가한 후에 가장 큰 99를 꺼내고

마지막 가방 무게가 10일 때 남은 96, 90, 65 중에서 가장 큰 96을 꺼낸다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		long max = 0;

		PriorityQueue<Gem> gems = new PriorityQueue<>();
		PriorityQueue<Integer> bags = new PriorityQueue<>();
		PriorityQueue<Integer> values = new PriorityQueue<>(Comparator.reverseOrder());

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			int m = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			gems.offer(new Gem(m, v));
		}

		for (int i = 0; i < k; i++) {
			int c = Integer.parseInt(br.readLine());
			bags.offer(c);
		}

		while (!bags.isEmpty()) {
			int bag = bags.poll();

			while (!gems.isEmpty()) {
				Gem gem = gems.peek();

				if (gem.m > bag) break;

				gems.poll();
				values.offer(gem.v);
			}

			if (!values.isEmpty()) max += values.poll();
		}

		System.out.println(max);
	}

	static class Gem implements Comparable<Gem> {
		int m, v;

		Gem(int m, int v) {
			this.m = m;
			this.v = v;
		}

		@Override
		public int compareTo(Gem o) {
			return this.m != o.m ? this.m - o.m : o.v - this.v;
		}
	}
}

문제

접근 방식

맵의 최대 크기가 1000 * 1000이기 때문에

매번 벽을 기준으로 BFS나 DFS를 이용해 탐색하면 시간초과가 발생한다.

그래서 0을 기준으로 각 구역의 크기를 계산한 후에

1을 기준으로 상하좌우로 맞닿은 구역의 크기를 더해주면 되는데

이때 중복이 있을 수 있기 때문에 Set을 사용해서 처리해 주면 된다.

예를 들어 현재 벽과 맞닿은 구역이 1, 1, 2, 3 구역이라면

1 구역은 한 번만 계산하면 되기 때문에 중복을 처리해

1, 2, 3 구역의 크기를 한 번씩만 계산해 주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);

		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		int[][] map = new int[n][m];
		int[][] isVisited = new int[n][m];
		Queue<Pair> q = new ArrayDeque<>();

		for (int i = 0; i < n; i++) {
			input = br.readLine().split("");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(input[j]) * -1;
			}
		}

		Map<Integer, Integer> counts = new HashMap<>();
		int num = 1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == -1) continue;
				if (isVisited[i][j] != 0) continue;

				int cnt = 1;
				q.offer(new Pair(i, j));
				isVisited[i][j] = num;

				while (!q.isEmpty()) {
					Pair cur = q.poll();

					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.x + dx[dir];
						int ny = cur.y + dy[dir];

						if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
						if (isVisited[nx][ny] != 0 || map[nx][ny] == -1) continue;

						cnt++;
						isVisited[nx][ny] = num;
						q.offer(new Pair(nx, ny));
					}
				}

				counts.put(num++, cnt);
			}
		}

		Set<Integer> set = new HashSet<>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0) {
					sb.append(0);
					continue;
				}

				int cnt = 1;

				for (int dir = 0; dir < 4; dir++) {
					int nx = i + dx[dir];
					int ny = j + dy[dir];

					if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
					if (map[nx][ny] == -1) continue;

					set.add(isVisited[nx][ny]);
				}

				for (int c : set) cnt += counts.get(c);
				set.clear();

				sb.append(cnt % 10);
			}
			sb.append("\n");
		}

		System.out.println(sb);
	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

문제

접근 방식

스도쿠의 빈칸을 채우는 문제다.

특별한 규칙은 없기 때문에 백트래킹으로 매번 행과 열, 3*3칸을 확인해 주며

가능한 숫자들을 모두 시도해보아야 한다.

문제의 설명이 조금 헷갈렸는데 81 자리의 수가 제일 작은 경우라는 말이

81번째 칸을 말하는 게 아니라 9*9칸을 일렬로 늘어놨을 때

나오는 81자리 수를 말하는 것이기 때문에 백트래킹 자체를

1 ~ 9까지의 수를 오름차순으로 대입하다 보면 처음 나오는 결과가

가장 작은 수이기 때문에 그 이후는 탐색하지 않고 탐색을 끝내면 된다.

수들을 선택할 때마다 현재 행과 열, 구역에 해당 수의 사용여부를 기록하면

매번 행, 열, 구역을 확인하는 것보다 편리하게 백트래킹을 할 수 있다.

풀이

public class Main {

	static int tx = 0, ty = 0, cnt = 81;
	static int[][] map = new int[9][9];
	static boolean[][] isUsedX = new boolean[9][10];
	static boolean[][] isUsedY = new boolean[9][10];
	static boolean[][] isUsedTT = new boolean[10][10];
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input;

		for (int i = 0; i < 9; i++) {
			input = br.readLine().split("");
			for (int j = 0; j < 9; j++) {
				int num = Integer.parseInt(input[j]);
				map[i][j] = num;
				if (num != 0) {
					cnt--;
					isUsedX[i][num] = true;
					isUsedY[j][num] = true;
					isUsedTT[getTT(i, j)][num] = true;
				} else {
					tx = i;
					ty = j;
				}
			}
		}

		solve(0, 0);

		System.out.println(sb);
	}

	static boolean solve(int x, int y) {
		if (x == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(map[i][j]);
				}
				sb.append("\n");
			}
			return true;
		}

		if (map[x][y] != 0) {
			if (y == 8) {
				if (solve(x + 1, 0)) return true;
			}
			else {
				if(solve(x, y + 1)) return true;
			}
		} else {
			for (int i = 1; i <= 9; i++) {
				int tt = getTT(x, y);
				if (isUsedX[x][i] || isUsedY[y][i] || isUsedTT[tt][i]) {
					continue;
				}

				isUsedX[x][i] = true;
				isUsedY[y][i] = true;
				isUsedTT[tt][i] = true;
				map[x][y] = i;

				if (y == 8) {
					if (solve(x + 1, 0)) return true;
				}
				else {
					if(solve(x, y + 1)) return true;
				}

				map[x][y] = 0;
				isUsedX[x][i] = false;
				isUsedY[y][i] = false;
				isUsedTT[tt][i] = false;
			}
		}

		return false;
	}

	static int getTT(int i, int j) {
		if (i < 3) {
			if (j < 3) return 1;
			else if (j < 6) return 2;
			else return 3;
		} else if (i < 6) {
			if (j < 3) return 4;
			else if (j < 6) return 5;
			else return 6;
		} else {
			if (j < 3) return 7;
			else if (j < 6) return 8;
			else return 9;
		}
	}
}