[Baekjoon] 16197_두 동전

Gold IV

문제(출처: https://www.acmicpc.net/problem/16197)

---

< 두 동전 >

 

문제 풀이

 

bfs를 활용하여 각 동전을 상하좌우로 움직인다. 그 후 보드 범위를 확인하여 동전이 둘 다 보드 안이면 queue에 추가, 하나만 떨어졌으면 종료, 둘 다 떨어졌으면 계속해서 진행한다.

 

 

 - my solution (Java)

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

public class _16197_ { // 두 동전
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	static char[][] map;
	static Queue<int[]>queue;
	static int n,m;
	static int result=-1;

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		map=new char[n][m];
		queue=new LinkedList<>();
		for(int i=0; i<n; i++) {
			String s=bf.readLine();
			for(int j=0; j<m; j++) {
				map[i][j]=s.charAt(j);
				if(map[i][j]=='o')queue.add(new int[] {i,j,0}); // 동전 위치 저장
			}
		}
		search();
		System.out.println(result);
	}

	private static void search() {
		while(!queue.isEmpty()) {
			int []coin1=queue.poll();
			int []coin2=queue.poll();
			
			if(coin1[2]+1>10) continue;
			for(int i=0; i<4; i++) {
				int count=0;
				int x1=coin1[0]+dx[i];
				int y1=coin1[1]+dy[i];
				
				int x2=coin2[0]+dx[i];
				int y2=coin2[1]+dy[i];
				
				if(x1>=0 && x1<n && y1>=0 && y1<m && map[x1][y1]=='#') { // 이동하려는 칸이 벽이면 이동 x
					x1=coin1[0];
					y1=coin1[1];
				}else if(x1<0 || x1>=n || y1<0 || y1>=m) { // 바깥
					count+=1;
				}
				
				if(x2>=0 && x2<n && y2>=0 && y2<m && map[x2][y2]=='#') {
					x2=coin2[0];
					y2=coin2[1];
				}else if(x2<0 || x2>=n || y2<0 || y2>=m) {
					count+=1;
				}
				
				if(count==0 && !(x1==coin1[0] && y1==coin1[1] && x2==coin2[0] && y2==coin2[1])) { 
					queue.add(new int[] {x1,y1,coin1[2]+1});
					queue.add(new int[] {x2,y2,coin1[2]+1});
				}else if(count==1) { // 하나만 떨어짐
					result=coin1[2]+1;
					break;
				}
			}
			if(result>0) break;
		}	
	}
}

 

• Main
  • n, m 입력
  • map : 보드
  • queue : 동전의 [x좌표, y좌표, 횟수]를 저장
  • search 함수 호출
• search
  • queue에서 동전 2개의 위치를 꺼내옴
  • 버튼을 10번보다 많이 눌러야 한다면 다시 동전 꺼내기부터! 돌아감!
  • 동전 2개를 각각 상하좌우로 움직임 -> 각 동전이 이동하려는 칸이 벽이면 이동 x BUT 보드 밖이라면 count 증가  -> 동전이 하나도 밖으로 떨어지지 않았으며 원래 위치와 다르다면 queue에 추가! / 동전이 하나만 떨어졌다면 종료! / 동전이 둘 다 떨어졌다면 계속해서 수행

---

생각🤔

 

bfs를 수행하며 조건만 잘 설정해주면 금방 해결할 수 있었다.

 

---