[Baekjoon] 23747_와드

Gold V

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

---

< 와드 >

 

문제 풀이

 

bfs를 활용하여 문제를 해결하며 시간초과를 방지하기 위해 bufferedWriter를 사용했다.

 

 

 

 my solution (Java)

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

public class Main { // 와드
	static char arr[][];
	static boolean visited[][];
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	static int r,c;
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		r=Integer.parseInt(st.nextToken());
		c=Integer.parseInt(st.nextToken());
		
		arr=new char[r][c];
		visited=new boolean[r][c];
		for(int i=0; i<r; i++) {
			String str=bf.readLine();
			for(int j=0; j<c; j++) {
				arr[i][j]=str.charAt(j);
			}
		}
		
		st=new StringTokenizer(bf.readLine());
		int hr=Integer.parseInt(st.nextToken())-1;
		int hc=Integer.parseInt(st.nextToken())-1;
		
		String str=bf.readLine();
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i)=='W') {
				bfs(hr, hc);
			}else if(str.charAt(i)=='U') {
				hr-=1;
			}else if(str.charAt(i)=='D') {
				hr+=1;
			}else if(str.charAt(i)=='L') {
				hc-=1;
			}else if(str.charAt(i)=='R') {
				hc+=1;
			}
		}
		
		visited[hr][hc]=true;
		for(int i=0; i<4; i++) { // 최종 위치의 상하좌우
			int x=hr+dx[i];
			int y=hc+dy[i];
			if(x>=0 && x<r && y>=0 && y<c && !visited[x][y]) {
				visited[x][y]=true;
			}
		}
		
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				if(visited[i][j]) {
					bw.write(".");
				}else {
					bw.write("#");
				}
			}
			bw.write("\n");
		}
		bw.flush();
	}
	private static void bfs(int hr, int hc) {
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {hr,hc});
		visited[hr][hc]=true;
		
		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			for(int i=0; i<4; i++) {
				int x=temp[0]+dx[i];
				int y=temp[1]+dy[i];
				if(x>=0 && x<r && y>=0 && y<c && !visited[x][y]) {
					if(arr[temp[0]][temp[1]]==arr[x][y]) {
						visited[x][y]=true;
						queue.add(new int[] {x,y});
					}
				}
			}
		}
		
	}
}

 

Main

- 격자의 크기 (r, c) 입력

- arr : 격자 정보 저장

  visited: 방문 여부 저장

- 한별이의 위치 (Hr, Hc) 입력

- 여행 기록 문자열 입력 후 U D L R 이면 상하좌우에 맞게 좌표 이동/ W이면 bfs 함수 호출

- 최종 위치에서의 상하좌우 방문 표시

- visited 배열을 순환하며 시야에 들어있는 칸인지 아닌지 판별 후 출력

 

bfs

- queue에 x좌표, y 좌표 입력 및 방문 표시

- queue가 빌 때까지 반복 -> 상하좌우로 이동하여 현재 위치와 같은 영역이라면 queue에 저장 및 방문 표시

 

---

생각🤔

 

---