[백준] 1074 Z #JAVA

 

BAEKJOON [1074] Z

---

 

 

문제

---

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

 

 

입력 & 출력

---

 

예제입력	출력
2 3 1	11

 

예제입력	출력
3 7 7	63

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input, " ");
		
		int N = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		System.out.println(zVisit(N, r, c));
	}
	
	public static int zVisit(int N, int r, int c) {
		
		if(N == 0){
			return 0;
		} else {
			int dist = 1<<(N-1);	// 좌표를 움직일 거리
			
			if(r<dist && c<dist) return zVisit(N-1, r, c);								//1 
			else if(r<dist && c>=dist) return (dist*dist) + zVisit(N-1, r, c-dist);		//2
			else if(r>=dist && c<dist) return (dist*dist)*2 + zVisit(N-1, r-dist, c);	//3
			else return (dist*dist)*3 + zVisit(N-1, r-dist, c-dist);					//4
		}
	}
}

 

 

??

---

재귀를 사용

 

 

 

 

 

References

---

• 백준 1074

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)