[SWEA/JAVA] 2805 농작물 수확

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB

SW Expert Academy

 

 

 

두 가지 방법으로 풀었다.

1번은 그냥 규칙찾기.

맨 윗줄부터 가운데 한칸, 가운데 세칸... 이런식으로 증가하다가 n/2번째 줄부터 줄어들어간다

이 규칙을 적용해서 풀면.. 쉽게 풀림!

 

// 1번 방법 : 규칙 찾기
import java.util.Scanner;
public class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int testCase = sc.nextInt();
		
		for(int tc=1; tc<=testCase; tc++){
			
			int n = sc.nextInt();
			int [][]map = new int[n][n];
			String str;
			int sum = 0;
			int idx = n/2;
			for(int i=0; i<n; i++){
				str = sc.next();
				for(int j=0; j<n; j++){
					if(i<= n/2 && j >= idx && j <= n-idx-1){
						sum += str.charAt(j) - '0';
					}else if(i>n/2 && j >= idx && j <= n-idx-1){
						sum += str.charAt(j) - '0';
					}
				}
				if(i < n/2) idx--;
				else idx ++;
				
			}
			System.out.println("#"+tc + " " + sum);
		}
	}
}

 

2번 방법은 농작물 수확의 범위가... 밭의 정가운데부터 bfs로 퍼지니까.. bfs로 한번 풀어봤다.

 

// 2번 방법 : bfs
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	static class pair{
		int y, x;

		public pair(int y, int x) {
			this.y = y;
			this.x = x;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int testCase = sc.nextInt();
		
		for(int tc=1; tc<=testCase; tc++){
			
			int n = sc.nextInt();
			int [][]map = new int[n][n];
			for(int i=0; i<n; i++){
				String str = sc.next();
				for(int j=0; j<n; j++){
					map[i][j] = str.charAt(j)-'0';
				}
			}
			
			Queue<pair> que = new LinkedList<>();
			que.add(new pair(n/2, n/2));
			
			int sum = map[n/2][n/2], cnt = 0;
			boolean [][] visited = new boolean [n][n];
            visited[n/2][n/2] = true;
			int [][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
			loop:while(!que.isEmpty()){
				pair p = que.poll();
				
				for(int i=0; i<4; i++){
					int ny = p.y + delta[i][0];
					int nx = p.x + delta[i][1];
					if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
					if(!visited[ny][nx]){
						que.add(new pair(ny, nx));
						visited[ny][nx] = true;
						sum += map[ny][nx];
						if(ny == 0 || nx == 0 || ny == n-1 || nx == n-1) cnt++;
						if(cnt == 4 ){
							break loop;
						}
					}
				}
				
			}
			System.out.println("#"+tc + " " + sum);
		}
	}
}

 

새벽에 한번 풀어볼까 해서 시작했는데 bfs는 코드도 더 길고.. 시간차이는 거의 없고 메모리는 훨씬 잡아먹고... 역시 그냥 규칙찾는게 최고다.