[문제링크]

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

0. 한번의 클릭으로 하나 이상의 칸을 처리할 수 있는건 0인 칸 뿐이다

 

1. 미리 지뢰가 아닌 칸의 개수를 세둔다 (cnt)

 

2. 주변 지뢰의 갯수로 정답 배열을 미리 만들어놓고, 0이면서 처리되지 않은 칸에 대해서만 재귀로 주변 처리

  - 한 칸 처리할때마다 cnt에서 1씩 뺀다

 

3. 모든 0에 대해 처리하고 나면, 나머지 칸들은 하나하나 직접 눌러줘야한다 (남은 cnt만큼)

 

4. 0을 누른 횟수 + 나머지를 누른 횟수 = 정답

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			N = pint(br.readLine());
			map = new int[N][N];
			ansMap = new int[N][N];
			
			int pressCnt=0;//몇번 눌러야 하는가?
			cnt=0;//지뢰가 아닌 땅 cnt
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j]=s.charAt(j);
					if(map[i][j]=='.')cnt++;
				}
			}
			//정답배열 생성
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					for (int x = Math.max(i-1, 0); x < Math.min(i+2, N) ; x++) {
						for (int y = Math.max(j-1, 0); y < Math.min(j+2, N); y++) {
							if(map[x][y]=='*')ansMap[i][j]++;
						}
					}
				}
			}
			
			//모든 0부터 눌러본다
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(ansMap[i][j]==0 && map[i][j]=='.') {
						press(i,j);
						pressCnt++;
					}
				}
			}

			sb.append("#").append(testcase).append(" ").append(pressCnt+cnt).append("\n");
			
		}System.out.println(sb);
	}
    
	static int cnt,N;
	static int[][]map;
	static int[][]ansMap;
	static int[]dx = {1,1,0,-1,-1, -1, 0, 1};
	static int[]dy = {0,1,1, 1, 0, -1,-1,-1};
    
	static void press(int x, int y) {
		if(ansMap[x][y]!=0) {
			cnt--;
			map[x][y]=ansMap[x][y];
		}
		else {
			cnt--;
			map[x][y]=0;
			for (int i = 0; i < 8; i++) {
				int tx = x+dx[i], ty=y+dy[i];
				if(tx<0||tx>=N||ty<0||ty>=N||map[tx][ty]!='.')continue;
				press(x+dx[i],y+dy[i]);
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

[문제링크]

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

0. x,y지점에서 총 m칸, 최대 무게 c를 고려해 채취할 수 있는 꿀의 최대 가치는 항상 동일하다

  - 미리 연산해서 저장 후 활용한다

 

1. 위에서 구한 가치들 중, 구간이 겹치지 않으면서 가치의 합이 최대가 되는 두 구역을 찾는다

 

2. 가치가 큰 순서로 정렬한다

  - 최대 가치 구간을 한 구간으로 잡고 그리디하게 계산한 최댓값이 최댓값이 아니려면

  - 최대 가치 구간과 영역이 겹치는 다른 구간에서 나온 값만이 가능하다

 

3. 영역이 겹치는 구간의 수는 2*m-1개로, 정렬된 구간을 그만큼만 살펴보면

  - 그리디하게 구한 결과의 가능한 모든 반례를 고려한 결과가 나온다

 

* 최대 가치를 가지는 영역 X와, 이에 속하지 않는 영역중 최대 가치를 가진 Y의 합 : 그리디한 해결법 으로 생각하면

  - X+Y의 가치보다 큰 값은 X와 영역이 일부 겹치는 X'들이 서로 합쳐졌을때만 가능하다

 

  - m이 3이라면, n이 충분할 때 겹치는 영역은 최대 5개(자기 자신 포함) 

  - 1위가 최대영역 X이고, 2,3,4,5위가 X와 영역을 공유할 때 그리디한 답은 1위 + 6위

  - 2,3,4,5위의 해답만이 1+6위의 결과를 넘을 수 있다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = pint(st.nextToken());
			m = pint(st.nextToken());
			c = pint(st.nextToken());
			map = new int[n][n];
			for (int i = 0; i < n; i++) {
				st=new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			collect = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n-m+1; j++) {
					int temp =calMax(i,j,0,0,0); 
					collect.add(new int[] {i, j, temp});
				}
			}
			
			Collections.sort(collect, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o2[2]-o1[2];
				}
			});
			
			int max=0, len = Math.min(m*2-1, n-m+1);
			for (int i = 0; i < len; i++) {
				int[] fst = collect.get(i);
				for (int j = i+1; j < collect.size(); j++) {
					int[] snd = collect.get(j);
					if(fst[0]==snd[0] && Math.abs(fst[1]-snd[1])<m)continue;
					
					if(max<fst[2]+snd[2]) {
						max=fst[2]+snd[2]; break;
					}
				}
			}
			sb.append("#").append(testcase).append(" ").append(max).append("\n");
		}System.out.println(sb);
	}
    
	static int n,m,c;
	static int[][]map;
	static ArrayList<int[]>collect;
    
	static int calMax(int i,int j, int cost, int wid, int cnt) {
		if(wid>c)return 0;
		if(cnt==m) {
			return cost;
		}
		int temp=0;
		temp = calMax(i,j+1, cost+map[i][j]*map[i][j], wid + map[i][j], cnt+1);
		temp = Math.max(temp, calMax(i,j+1, cost, wid, cnt+1));
		return temp;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

[문제링크]

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

0. state 클래스로 정보를 관리 (x좌표, y좌표, 이전이동, 이동횟수)

 

1. bfs처럼 진행하되, 항상 목표지점으로 다가가는 이동이 최적의 이동이다

  - 현재 좌표와 목표좌표를 비교, 나아가야 할 방향을 결정한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution{
	
	static class state {
		public int x,y,prev,cost;
		public state(int x, int y, int prev, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.prev = prev;
			this.cost = cost;
		}
	}
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int sx = pint(st.nextToken());
			int sy = pint(st.nextToken());
			int dx = pint(st.nextToken());
			int dy = pint(st.nextToken());
			
			Queue<state>qu=new LinkedList<>();
			
			if(sx==dx && sy==dy) {
				sb.append("#").append(testcase).append(" ").append(0).append("\n");
				continue;
			}
			
			if(sx<dx)qu.offer(new state(sx+1,sy,1,1));
			else qu.offer(new state(sx-1,sy,1,1));
			if(sy<dy)qu.offer(new state(sx,sy+1,2,1));
			else qu.offer(new state(sx,sy-1,2,1));
			
			while(true) {
				state cur = qu.poll();
				System.out.println(cur.x+" "+cur.y);
				if(cur.x==dx && cur.y==dy) {
					sb.append("#").append(testcase).append(" ").append(cur.cost).append("\n");
					break;
				}
				
				if(cur.prev==2) {
					if(cur.x<dx)qu.offer(new state(cur.x+1, cur.y, 1, cur.cost+1));
					else qu.offer(new state(cur.x-1, cur.y, 1, cur.cost+1));
				}
				else {
					if(cur.y<dy)qu.offer(new state(cur.x, cur.y+1, 2, cur.cost+1));
					else qu.offer(new state(cur.x, cur.y-1, 2, cur.cost+1));
				}
				
			}
		}System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

[문제링크]

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

0. 가장 먼 점이 원점으로 이동할 때까지, 먼저 원점에 도달한 점들은 +1 -1 운동을 반복하게 된다

  - 모든 점들의 2로 나눈 나머지가 같지 않다면, 점들의 움직임이 일치하지 않아 한 점으로 모이는게 불가능하다

 

1. 입력받으며, 모든 수가 홀수 or 짝수로 통일되있는지 확인한다

  - 통일되있지 않으면, -1을 출력

 

2. 동시에, 입력값중 최댓값을 탐색한다

  - 모든 값이 홀/짝수로 통일되 있다면, 최댓값이 원점에 도달하는 순간 종료된다

 

3. 매 초 이동량의 누적값을 구하여 그 값이 max보다 크면서 max와의 차이가 짝수일 때 종료한다

 

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

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			int N = pint(br.readLine());
			int[] len = new int[N];
			int sum=0;
			int cnt=0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			len[0]= Math.abs(pint(st.nextToken())) + Math.abs(pint(st.nextToken()));
			int max=len[0];
			for (int i = 1; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				len[i]= Math.abs(pint(st.nextToken())) + Math.abs(pint(st.nextToken()));
				max=Math.max(max, len[i]);
				if(len[i]%2 != len[i-1]%2) {
					cnt=-1;
				}
			}
			
			if(cnt==0) {
				while(true) {
					boolean isE=true;
					if(sum<max || (max-sum)%2!=0) {
						isE=false;
					}
					if(isE)break;
					sum+=++cnt;
				}
			}
			sb.append("#").append(testcase).append(" ").append(cnt).append("\n");
			
		}System.out.println(sb);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

[문제링크]

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

0. 현재 파이프의 모양 - 인접 파이프의 모양 에 따라 갈수 있는지 없는지 여부가 결정된다

  - 총 4방향이므로, 4개의 bit에 bitmask로 저장해 정보를 나타낸다.

 

1. 입력값(0~7)에 따라 해당하는 bitmask정보를 부여한다

 

2. 시작점에서 time만큼 bfs를 돌며

  - 현재 노드에서 상/하/좌/우 통로가 존재하고 + 진행 노드에서 하/상/우/좌 통로가 존재한다면

  - 진행 가능, 큐에 넣는다

  - 방문체크 대신 큐에 넣을때 자기 위치의 값을 0으로 바꿔 재방문을 방지한다

 

3. time이 다 지났다면 (혹은 도중에 탐색을 마쳐 qu가 비었다면)

  - 방문할때마다 1씩 증가시켜준 cnt를 출력, 종료한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			int x = pint(st.nextToken())+1;
			int y = pint(st.nextToken())+1;
			int t = pint(st.nextToken());
			
			int[][] map = new int[n+2][m+2];
			
			for (int i = 1; i < n+1; i++) {
				st=new StringTokenizer(br.readLine()," ");
				for (int j = 1; j < m+1; j++) {
					int temp = pint(st.nextToken());
					if(temp==1)map[i][j]=0b1111;
					else if(temp==2)map[i][j]=0b1100;
					else if(temp==3)map[i][j]=0b0011;
					else if(temp==4)map[i][j]=0b1001;
					else if(temp==5)map[i][j]=0b0101;
					else if(temp==6)map[i][j]=0b0110;
					else if(temp==7)map[i][j]=0b1010;
				}
			}
			
			Queue<int[]> qu = new LinkedList<int[]>();
			qu.add(new int[] {x,y});
			int cnt=0;
			int time=0;
			while(time++<t && !qu.isEmpty()) {
				int len = qu.size();
				
				for (int i = 0; i < len; i++) {
					int[] cur=qu.poll();
					int temp = map[cur[0]][cur[1]];
					if(temp==0)continue;
					
					if((temp&1<<3)!=0 && (map[cur[0]-1][cur[1]]&1<<2)!=0)
						qu.offer(new int[] {cur[0]-1,cur[1]});
					if((temp&1<<2)!=0 && (map[cur[0]+1][cur[1]]&1<<3)!=0)
						qu.offer(new int[] {cur[0]+1,cur[1]});
					if((temp&1<<1)!=0 && (map[cur[0]][cur[1]-1]&1<<0)!=0)
						qu.offer(new int[] {cur[0],cur[1]-1});
					if((temp&1<<0)!=0 && (map[cur[0]][cur[1]+1]&1<<1)!=0)
						qu.offer(new int[] {cur[0],cur[1]+1});
					
					cnt++;
					map[cur[0]][cur[1]]=0;
				}
			}
			sb.append("#").append(testcase).append(" ").append(cnt).append("\n");
		}//end of tc
		System.out.println(sb);
	}

	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

'알고리즘 문제 풀이 > SWEA' 카테고리의 다른 글

[SWEA] 2115 - 벌꿀채취  (0) 2021.04.22
[SWEA] 8382 - 방향전환  (0) 2021.04.19
[SWEA] 8458 - 원점으로 집합  (0) 2021.04.19
[SWEA] 5656 - 벽돌깨기  (0) 2021.04.15
[SWEA] 4014 - 활주로 건설 / [백준] 14890 - 경사로  (0) 2021.04.13
[SWEA] 1249 - 보급로  (0) 2021.04.12
[SWEA] 5644 - 무선충전  (0) 2021.04.12

[문제링크]

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

0. shoot함수 : n번째 구슬을 모든 경우의 수에 대해 쏴보고, n+1번째로 재귀하는 함수

  - remove함수 : x, y좌표의 벽돌이 깨졌을 경우 모든 벽돌을 재귀로 깨는 함수

  - getDown함수 : 벽돌을 깬 후 모든 벽돌을 빈공간 없이 아래로 쌓는 함수

 

1. shoot함수가 모든 경우의 수에 대해 remove -> getDown 해본다

 

2. n번 구슬을 쐈을때 남아있는 ball값과 min을 비교, 갱신

 

* ball(remain)값을 인자로 넘기지 말고 전역변수로 관리할 수 있을것같은데, 피곤해서 포기

 

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

public class Solution{
	
	static int n,w,h,ball,min;
	static int[][]map;
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = pint(st.nextToken());
			w = pint(st.nextToken());
			h = pint(st.nextToken());
			ball = 0;
			map = new int[h][w];
			
			for (int i = 0; i < h; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < w; j++) {
					map[i][j]=pint(st.nextToken());
					if(map[i][j]!=0)ball++;
				}
			}
			min=ball;
			shoot(0,ball);
			
			sb.append("#").append(testcase).append(" ").append(min).append("\n");
		}
		System.out.println(sb);
	}
	
	static void shoot(int cnt, int remain) {
		if(cnt==n) {
			min=Math.min(min, remain);
			return;
		}
		//현재 정보 백업
		int[][]backup = new int[h][w];
		for (int x = 0; x < h; x++) {
			for (int y = 0; y < w; y++) {
				backup[x][y]=map[x][y];
			}
		}
		int ballBackup=ball;

		for (int i = 0; i < w; i++) {
			// 정보 원상복구
			for (int x = 0; x < h; x++) {
				for (int y = 0; y < w; y++) {
					map[x][y]=backup[x][y];
				}
			}
			ball=ballBackup;

			for (int j = 0; j < h; j++) {
				if(map[j][i]!=0) {
					remove(j,i); // 제거하고
					getDown(); // 아래로 정렬하고
					break;
				}
			}
			shoot(cnt+1, ball); // 다음 발사로 재귀
			
		}
	}
	
	static void remove(int x, int y) {
		int c = map[x][y];
		map[x][y]=0;
		--ball;
		for (int j = 0; j < 4; j++) {
			int tx=x, ty=y;
			for (int i = 1; i < c; i++) {
				tx += dx[j];
				ty += dy[j];
				if(tx<0 || tx>=h || ty<0 || ty>=w)break;
				if(map[tx][ty]!=0)remove(tx,ty);
			}
		}
	}
	
	static void getDown() {
		for (int i = 0; i < w; i++) {
			int cnt=h-1;
			for (int j = h-1; j >=0 ; j--) {
				if(map[j][i]!=0) {
					int t = map[j][i];
					map[j][i]=0;
					map[cnt--][i]=t;
				}
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

[문제링크]

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

[문제링크]

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

0. 활주로 건설이 불가능한 경우는 2가지이다

  - 2칸 이상 차이가 나는 경우

  - 1칸 차이가 나지만 X칸만큼의 공간이 존재하지 않을 경우

 

1. 2칸 이상 차이가 난다면 불가능 처리한다

 

2. 높이가 동일한 경우, cnt로 갯수를 세가며 진행한다

  - 올라가야하는 상황이 생겼을 때, cnt가 X보다 크거나 같아야만 진행 가능하다

  - 올라간 칸에서부터 시작하므로 cnt값을 1로 초기화

 

3. 내려가야하는 상황이 생겼다면 앞에 X칸의 공간이 동일한 높이로 존재해야 진행 가능하다

  - 반목문으로 X칸의 높이를 확인, 다르면 불가능 처리한다

  - 전부 같다면, 현재 위치가 j였을때 j+X칸에서부터 다시 시작하므로, j+X-1으로 포인터를 옮긴다

  - 이때, j+X-1칸은 경사로의 마지막 칸이므로, cnt는 0으로 초기화

 

4. 위 과정을 모든 행/열에 대해 실행해주고 가능한 경우를 카운트

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

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int x = pint(st.nextToken());
			int[][]map = new int[n][n];

			for (int i = 0; i < n; i++) {
				st=new StringTokenizer(br.readLine()," ");
				for (int j = 0; j < n; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			
			int possibleCnt=0;
			
			for (int i = 0; i < n; i++) {
				//i번째 Row의 불가능 가능 여부를 탐색
				boolean isP = true;
				
				//1. 2칸 이상 차이나면 불가
				for (int j = 1; j < n; j++) {
					if(Math.abs(map[i][j] - map[i][j-1]) >=2)isP=false;
				}if(!isP)continue;
				
				//2. 1칸 올라|내려 가야하는데, 뒤|앞에 공간이 x칸 없으면 불가
				int prev=map[i][0];
				int cnt=1;
				for (int j = 1; j < n; j++) {
					//같으면 +
					if(prev == map[i][j])cnt++;
					else if(prev< map[i][j]) {
						//올라갈 때
						if(cnt>=x) {
							//ok
						}
						else {
							isP=false;
						}
						prev=map[i][j];
						cnt=1;//cnt초기화
					}
					else {
						//내려갈 때
						//앞에 x칸이 다 같은 높이로 존재하는지 확인
						//만족한다면, x 앞칸으로 포인터(j)이동
						prev = map[i][j];
						cnt=1;
						for (int j2 = 1; j2 < x; j2++) {
							if(j+j2 >= n)break;
							if(prev==map[i][j+j2])cnt++;
						}
						if(cnt!=x)isP=false;
						j = j+x-1;
						cnt=0;//cnt초기화
					}
				}
				if(isP)possibleCnt++;
			}
			
			for (int i = 0; i < n; i++) {
				//i번째 Col의 불가능 가능 여부를 탐색
				boolean isP = true;
				
				//1. 2칸 이상 차이나면 불가
				for (int j = 1; j < n; j++) {
					if(Math.abs(map[j][i] - map[j-1][i]) >=2)isP=false;
				}if(!isP)continue;
				
				//2. 1칸 올라|내려 가야하는데, 뒤|앞에 공간이 x칸 없으면 불가
				int prev=map[0][i];
				int cnt=1;
				for (int j = 1; j < n; j++) {
					//같으면 +
					if(prev == map[j][i])cnt++;
					else if(prev< map[j][i]) {
						//올라갈때
						if(cnt>=x) {
							//ok
						}
						else {
							isP=false;
						}
						prev=map[j][i];
						cnt=1;//cnt초기화
					}
					else {
						//내려갈 때
						//앞에 x칸이 다 같은 높이로 존재하는지 확인
						//만족한다면, x 앞칸으로 포인터(j)이동
						prev = map[j][i];
						cnt=1;
						for (int j2 = 1; j2 < x; j2++) {
							if(j+j2 >= n)break;
							if(prev==map[j+j2][i])cnt++;
						}
						if(cnt!=x)isP=false;
						j = j+x-1;
						cnt=0;
					}
					
				}
				if(isP)possibleCnt++;
			}
			
			sb.append("#").append(testcase).append(" ").append(possibleCnt).append("\n");
		}
		System.out.println(sb);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

'알고리즘 문제 풀이 > SWEA' 카테고리의 다른 글

[SWEA] 2115 - 벌꿀채취  (0) 2021.04.22
[SWEA] 8382 - 방향전환  (0) 2021.04.19
[SWEA] 8458 - 원점으로 집합  (0) 2021.04.19
[SWEA] 1953 - 탈주범검거  (0) 2021.04.15
[SWEA] 5656 - 벽돌깨기  (0) 2021.04.15
[SWEA] 1249 - 보급로  (0) 2021.04.12
[SWEA] 5644 - 무선충전  (0) 2021.04.12

[문제링크]

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

0. 모든 경우의 수를 탐색 - BFS

  - 같은 공간 큰 cost를 가지고 접근할 경우 더이상 진행하지 않으므로, DFS보다 수행횟수가 적다

  - 외각을 -1로 감싸 나가지 못하도록 처리

 

1. (1, 1) 좌표부터 bfs 진행 후 N,N좌표의 cost가 최소 cost

 

개선점

1. 현재 bfs는 2-3-4순으로 진입시 3,4에 대해선 진행하지 않지만, 4-3-2순으로 진입시 4,3,2 전부 실행하게된다.

  - priority queue를 이용해 해결 가능

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution{
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			int N = pint(br.readLine());
			int[][] map = new int[N+2][N+2];
			int[][] cost = new int[N+2][N+2];
			
			//외곽설정, cost초기화
			for (int i = 0; i < N+2; i++) {
				map[0][i]=-1;map[N+1][i]=-1;
				map[i][0]=-1;map[i][N+1]=-1;
				Arrays.fill(cost[i], Integer.MAX_VALUE);
			}
			
			//입력받기
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i+1][j+1]=s.charAt(j)-'0';
				}
			}
			
			Queue<int[]> qu = new LinkedList<>();
			qu.offer(new int[] {1,1});
			cost[1][1]=0;
			
			while(!qu.isEmpty()) {
				int[]cur = qu.poll();
				int curCost = cost[cur[0]][cur[1]];
				
				//더 작은 코스트로 진행할 수 있다면
				for (int i = 0; i < 4; i++) {
					int tx=cur[0]+dx[i], ty=cur[1]+dy[i];
					
					if(map[ tx ][ ty ]!=-1 && curCost + map[ tx ][ ty ] < cost[ tx ][ ty ]) {
						qu.offer(new int[] {tx, ty});
						cost[ tx ][ ty ]=curCost+map[ tx ][ ty ];
					}
				}
			}
			sb.append("#").append(testcase).append(" ").append(cost[N][N]).append("\n");
		}
		System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

+ Recent posts