SWEA 2805 농작물 수확하기 풀이 java

문제로이동

SW Expert Academy

---

목차

 

---

---

풀이 과정

첫 시도엔 BFS를 떠올려 시도했습니다.

D3에 BFS가 나올리는 없어서 다시 생각해보니 다이아몬드 형태를 한 번에 더할 수 있겠다는 확신이 들었습니다.

0 - 1 - 2 - 1 - 0과 같이 점차 증가했다가 중간값에 도달하면 다시 감소하는 식을 구했습니다만,

해당 방법 이외에도 양 끝점에서 동시에 값을 더하는 방법이 있습니다.

for(int i =0;i<중간지점;i++)
{
	answer += 위쪽의 합
    	answer += 아래쪽의 합
}

 

이렇게 구현한다면 코드가 더 짧아질 수도 있습니다.

---

소스 코드

Java8 1차

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

public class Solution {
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int T,N,answer;
	static int field[][];
	static int visited[][];
	static Deque<Pos> dq = new ArrayDeque<>();
	static Pos[] direction = {new Pos(0,-1),new Pos(0,1),new Pos(-1,0),new Pos(1,0)};//상하좌우
	static class Pos{
		int x,y,depth;
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
		public Pos(int x, int y,int depth) {
			this.x = x;
			this.y = y;
			this.depth = depth;
		}
	}
	static void solution() {
		dq.clear();
		dq.add(new Pos(N/2,N/2,1));
		answer += field[N/2][N/2];
		visited[N/2][N/2]=1;
		while(!dq.isEmpty()) {
			Pos tmp = dq.pollFirst();
			if(tmp.depth>N/2)break;
			Deque<Pos> orderQ = new ArrayDeque<>();
			for(Pos dpos:direction) {
				int nx = tmp.x+dpos.x;
				int ny = tmp.y+dpos.y;
				if(0>nx || nx>=N || 0>ny || ny>=N) {
					orderQ.clear();
					break;}
				else {
					if(visited[ny][nx]==0)
						orderQ.add(new Pos(nx,ny));
				}
			}
			for(Pos oPos:orderQ) {
				answer+= field[oPos.y][oPos.x];
				visited[oPos.y][oPos.x] = 1;
				dq.add(new Pos(oPos.x,oPos.y,tmp.depth+1));
			}
		}
	}
	public static void main(String[] args) throws IOException{
		T = Integer.parseInt(bf.readLine());
		for(int t=1;t<=T;t++) {
			answer = 0;
			st = new StringTokenizer(bf.readLine());
			N = Integer.parseInt(st.nextToken());
			field = new int[N][N];
			visited = new int[N][N];
			for(int i =0;i<N;i++) {
				String tmp = bf.readLine();
				for(int j =0;j<N;j++) {
					field[i][j] = tmp.charAt(j)-48;
				}
			}
			solution();
			sb.append("#").append(t).append(" ").append(answer).append("\n");
		}
		System.out.println(sb);
	}
}

---

Java8 압축

import java.io.*;
public class Solution_new {
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();	
	public static void main(String[] args) throws IOException{
		int T = Integer.parseInt(bf.readLine());
		for(int t=1;t<=T;t++) {
			int answer = 0, N = Integer.parseInt(bf.readLine());
			int [][]field = new int[N][N];
			for(int i =0;i<N;i++) {
				String tmp = bf.readLine();
				for(int j =0;j<N;j++)field[i][j] = tmp.charAt(j)-48;
			}
			for(int i =0;i<N;i++)
				for(int j=Math.abs(N/2-i);j<=2*(N/2)-Math.abs(N/2-i);j++)
					answer+=field[i][j];
			sb.append("#").append(t).append(" ").append(answer).append("\n");
		}
		System.out.println(sb);
	}
}