코딩테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제를 의미한다.(피지컬을 요구)
이 책에선 완전탐색,시뮬레이션도 구현유형에 속한다고 표현했다.

예제 4-1 상하좌우

문제요약: 여행자가 N * N크기의 정사각형 공간 위에 서 있다. 이때 시작 좌표는1,1 이고 다음줄엔 L,R,U,D 문제가 반복적으로 나와있다 이때 정사각형 공간을 벗어나는 움직임은 무시된다. 이때 최종좌표를 구해라

구현코드:

import java.util.*;

public class Main{
	 static int[] dx ={0, 0, -1, 1};
     static int[] dy ={-1, 1,0 , 0};
     static String[] dmove ={"L", "R", "U" ,"D"};
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
		sc.nextLine();
        String[] move = sc.nextLine().split(" ");
        int x = 1;
        int y = 1;
        
        for(String mv : move ){
        	int xtemp = -1;
        	int ytemp = -1;
        	for(int i = 0; i < 4 ; i++){
            	if(dmove[i].equals(mv)){
                	xtemp = x + dx[i];
                    ytemp = y + dy[i];
                }
            }
            
            if(xtemp < 1 || xtemp > n || ytemp < 1 || ytemp > n){
            	continue;
            }
            x = xtemp;
            y = ytemp;
        }
        
        System.out.println(x+" "+y);
    }

}

코드해석:
L,R,U,D 가 들어오기 때문에 배열에 넣고 dx,xy값을 넣어논다.
그 후 입력값에 따라서 좌표를 이동하는데 좌표를 벗어나면 무효시키기 때문에
if(xtemp < 1 || xtemp > n || ytemp < 1 || ytemp > n) 조건을 추가한다.

예제 4-2 시각

문제요약:정수 N 이 입력되면 00시00분00초 부터 N시 59분59초 까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 수하는 프로그램을 작성하시오

구현코드:

import java.util.*;
public class Main{
	
	public static boolean check(int h, int m, int s){
    	if(h % 10 == 3 || m % 10 == 3 || m / 10 == 3 || s % 10 == 3 || s / 10 ==3){
        	return true;
        }
        return false;
    }
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cnt = 0;
        for(int i = 0; i <= n; i++){
        	for(int j = 0 ; j < 60; j ++){
            	for(int k = 0;k < 60; k++){
                	if(check(i, j, k)) cnt++;
                }
            }
        }
        System.out.println(cnt);	
    }
}

코드해석:
00시00분00초 부터 N시 59분59초 까지 수중에서 3이포함되는 모든 경우의 수를 구하는 문제이다. 완전탐색 문제라고 생각할 수 있다. 24시 까지 하더라도 86400 개의 수밖에 안되기 때문에 시간초과는 생각안해도 되는 문제이다.
3이 포함되는지 확인하는 방법은 시간을 10으로 나눈 나머지가 3일때, 분을 10으로 초를 10으로 나눈 나머지가 3,분, 초 를 10으로 나눈 몫이 3일때를 찾으면 된다.

실전문제 1.왕실의 나이트

문제요약:

예를들어 a1이라는 좌표가 주어졌을 때 나이트가 움직일 수 있는 방법을 구하는 문제이다.
답은 2.

구현코드:

package test;
import java.io.*;
import java.util.*;

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(),"");
		String str = br.readLine();
		int y = str.charAt(0)- 96;
		int x = str.charAt(1) -'0';
		int[] dy = {-1, 1, -1, 1, -2, 2, -2, 2};
		int[] dx = {2, 2, -2, -2, 1, 1, -1, -1};
		int cnt = 0;
		for(int i = 0; i < 8 ; i++){
			int ny = y +dy[i];
			int nx = x +dx[i];
			if(ny < 1 || ny > 8 || nx < 1 || nx > 8) continue;
			cnt ++;
		}
		System.out.println(cnt);
	}
}

코드해석:
Scanner 대신에 BufferedReader 가 속도측명에서 더 빠르기 때문에 연습겸 풀어보았다.
우선 한 줄을 읽어서 charAt으로 문자 하나씩 나누어 x,y 좌표를 구하고 나이트가 움직일 수 있는 8개의 방법이 좌표를 넘어가지 않는지 확인한 후에 값 cnt 를 해줍니다.

실전문제 2.게임 개발

문제요약:
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.

현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.

캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

입력
첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다.
(3 <= N, M <= 50)

둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방햔 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.

0 : 북쪽
1 : 동쪽
2 : 남쪽
3 : 서쪽

셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외각은 항상 바다로 되어 있다.

0 : 육지
1 : 바다
처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

출력
첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

입력 예시
4 4
1 1 0 // (1, 1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1

출력 예시
3

구현코드:

package test;
import java.io.*;
import java.util.*;

public class Main{
	public static int[][] map
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static int[][] visited
	public static int direction;
	public static void turnLeft(){
		direction++;
		if(direction == 4) direction = 0;
	}
	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 m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		direction = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		visited = new int[n][m];
		for(int i = 0;i < n;i++){
			st = new StringTokenizer(br.readLine());
			for(int j = 0;j < m; j++){
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int cnt = 1;
		visited[x][y] = 1;
		int turnCount = 0;
		while(true){
			turnLeft();
			int nx = x + dx[direction];
			int ny = y + dy[direction];
			if(map[nx][ny] == 0 && visited[nx][ny] == 0){
				visited[nx][ny] = 1;
				x = nx;
				y = ny;
				cnt += 1;
				turnCount = 0;
				continue;
			} else {
				turnCount += 1;
			}
			
			if(turnCount == 4){
				nx = x - dx[direction];
				ny = y - dy[direction];
				if(map[nx][ny] == 0){
					x = nx;
					y = ny;
				}else {
					break;
				}
				turnCount = 0;
			}
		}
		
		 System.out.println(cnt);
	}
}

코드해석:
BufferedReader와 StringTokenizer 를 이용하여 값을 입력받습니다. 문제 조건과 같이 구현하면 되는데 맨처음 문제를 이해하는 것도 쉽지 않습니다.
이 문제는 전형적인 시물레이션 문제이고 이 문제는 방향을 설정해서 그 방향을 갈 수있는지 확인하면 된다.
우선 북쪽을 0으로 두고 서 ,남 ,동 순으로 dx,dy를 배열에 저장해 두고.회전 할 때마다 ++ 해주고 4가 되었을 때 0으로 값을 할당해줍니다.
또한 왼쪽으로 회전 후 앞으로 갈 수있는지, 바다가 아닌지 판단한 후에 갈 수있다면. 방문했다 표시하고 회전수를 초기화,방문수++ 해줍니다.
아닐경우 회전을 시켜줍니다. 그리고 회전 수가 4일 경우 뒤로 갈 수있는지 없는지 판단하고 바다라면 break, 뒤로 갈 수있다면 뒤로 가 줍니다.