개발/알고리즘

백준 16946번 벽 부수고 이동하기4

dev-yoon-jerry 2022. 6. 2. 18:40

https://www.acmicpc.net/problem/16946

 

16946번: 벽 부수고 이동하기 4

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이

www.acmicpc.net

그냥 bfs, dfs 문제이겠거니 해서 풀었는데 시간초과가 떠서 당황했다.

처음 풀이

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

public class Main {
		static int N,M;
		static int[][] map;
		static int[][] resultMap;
		static boolean [][] visited;
		static int[][] nextDir = {{0,1},{0,-1},{1,0},{-1,0}};
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			resultMap = new int[N][M];
			for(int i=0;i<N;i++) {
				String line = br.readLine();
				for(int j=0;j<M;j++) {
					map[i][j] = line.charAt(j)-'0';
				}
			}
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					resultMap[i][j]=getResult(i,j);
				}
			}
			StringBuffer sb = new StringBuffer();
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					sb.append(resultMap[i][j]);
				}
				sb.append("\n");
			}
			System.out.println(sb);
		}
		public static int getResult(int n,int m) {
			if(map[n][m]==0) return 0;
			visited = new boolean[N][M];
			map[n][m]=0;
			Queue <int[]> q = new ArrayDeque<>();
			q.add(new int[] {n,m});
			int visitCount = 0;
			while(!q.isEmpty()) {
				int [] now = q.poll();
				int nowI = now[0];
				int nowJ = now[1];
				if(visited[nowI][nowJ]) continue;
				visited[nowI][nowJ] = true;
				visitCount++;
				for(int k=0;k<4;k++) {
					int nextI = nowI + nextDir[k][0];
					int nextJ = nowJ + nextDir[k][1];
					if(nextI < 0 || nextI >=N || nextJ <0 || nextJ >=M) continue;
					if(visited[nextI][nextJ]) continue;
					if(map[nextI][nextJ]==0) {
						q.add(new int[] {nextI,nextJ});
					}
				}
			}
			map[n][m]=1;
			return visitCount%10;
		}
}

getResult는 벽인경우 벽을 허물고 주변 빈공간을 탐색한 뒤 다시 벽을 복구하도록 했다.

뭔가 줄이는 방법이 있겠지 해서 여러번 시도해봤는데, 한 2시간 생각하다가 벽기준이 아니라 빈칸 기준으로 생각하면 시간을 줄일 수 있다는 것을 알게되었다.

벽1 빈칸그룹1 벽2
빈칸그룹2 벽3 빈칸그룹3
벽4 빈칸그룹4 벽5

벽1 = 1 + 빈칸그룹1 + 빈칸그룹2.    벽2 = 1 + 빈칸그룹1 + 빈칸그룹3 ....
기존 방식대로라면 벽마다 빈칸그룹을 다 탐색하는데, 먼저 빈칸그룹을 탐색해서 몇개나 갈 수 있는지 체크하면 연산을 줄일 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
		static int N,M;
		static int[][] map;
		static int[][] resultMap;
		static int[][] group;
		static int[][] nextDir = {{0,1},{0,-1},{1,0},{-1,0}};
		static int groupNum;
		static List<Integer> groupMemberCount;
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			resultMap = new int[N][M];
			group = new int[N][M];
			groupMemberCount = new ArrayList<>();
			groupMemberCount.add(0);
			for(int i=0;i<N;i++) {
				String line = br.readLine();
				for(int j=0;j<M;j++) {
					map[i][j] = line.charAt(j)-'0';
				}
			}
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(map[i][j]==1) continue; //벽
					if(group[i][j] != 0) continue; // 이미 그룹이 있음
					groupMemberCount.add(getGroup(i,j));
				}
			}
			StringBuffer sb = new StringBuffer();
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					sb.append(getResult(i,j));
				}
				sb.append("\n");
			}
			System.out.println(sb);
		}
		public static int getGroup(int n,int m) {
			Queue <int[]> q = new ArrayDeque<>();
			q.add(new int[] {n,m});
			int visitCount = 0; //그룹에서 이동할수 있는칸 수 카운트
			groupNum++;
			while(!q.isEmpty()) {
				int [] now = q.poll();
				int nowI = now[0];
				int nowJ = now[1];
				if(group[nowI][nowJ]!=0) continue; // 이미 그룹이 있음
				group[nowI][nowJ] = groupNum;
				visitCount++;
				for(int k=0;k<4;k++) {
					int nextI = nowI + nextDir[k][0];
					int nextJ = nowJ + nextDir[k][1];
					if(nextI < 0 || nextI >=N || nextJ <0 || nextJ >=M) continue;
					if(group[nextI][nextJ]!=0) continue; // 탐색할 칸이 이미 그룹이 있음
					if(map[nextI][nextJ]==0) { // 그룹없는 빈칸
						q.add(new int[] {nextI,nextJ});
					}
				}
			}
			return visitCount;
		}
		public static int getResult(int i,int j) {
			if(map[i][j]==0) return 0;
			int visitCount = 1; // 벽을 부수므로 1
			for(int k=0;k<4;k++) { // 사방 4칸의 그룹의 갈수있는 칸 수 더하기
				int nextI = i + nextDir[k][0];
				int nextJ = j + nextDir[k][1];
				if(nextI < 0 || nextI >=N || nextJ <0 || nextJ >=M) continue;
				if(map[nextI][nextJ]==0) {
					visitCount += groupMemberCount.get(group[nextI][nextJ]); // 해당그룹의 칸 수
				}
			}
			return visitCount%10;
		}
}

group[][] 에 해당 칸의 그룹번호를 넣게 했고 (0인경우 그룹 없음) 이렇게 하니까 이전버전의 visited 체크도 한번에 할 수 있었다.
groupMemberCount는 0번을 더미로 넣고 해당 그룹번호를 넣으면 몇칸 이동할 수 있는지 뽑을 수 있게 했다.

이번엔 맞겠지 해서 돌렸는데 또..

왜틀린지 몰라서 반례를 찾다가

빈칸그룹1 벽1 빈칸그룹2
벽2 빈칸그룹2 빈칸그룹2
빈칸그룹2 빈칸그룹2 빈칸그룹2

상하좌우에 같은 빈칸그룹이 있으면 여러번 연산되는 것을 알게 되었다. ex) 벽1 = 1 + 빈칸그룹1 + 빈칸그룹2 + 빈칸그룹2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
		static int N,M;
		static int[][] map;
		static int[][] resultMap;
		static int[][] group;
		static int[][] nextDir = {{0,1},{0,-1},{1,0},{-1,0}};
		static int groupNum;
		static List<Integer> groupMemberCount;
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			resultMap = new int[N][M];
			group = new int[N][M];
			groupMemberCount = new ArrayList<>();
			groupMemberCount.add(0);
			for(int i=0;i<N;i++) {
				String line = br.readLine();
				for(int j=0;j<M;j++) {
					map[i][j] = line.charAt(j)-'0';
				}
			}
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(map[i][j]==1) continue; //벽
					if(group[i][j] != 0) continue; // 이미 그룹이 있음
					groupMemberCount.add(getGroup(i,j));
				}
			}
			StringBuffer sb = new StringBuffer();
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					sb.append(getResult(i,j));
				}
				sb.append("\n");
			}
			System.out.println(sb);
		}
		public static int getGroup(int n,int m) {
			Queue <int[]> q = new ArrayDeque<>();
			q.add(new int[] {n,m});
			int visitCount = 0; //그룹에서 이동할수 있는칸 수 카운트
			groupNum++;
			while(!q.isEmpty()) {
				int [] now = q.poll();
				int nowI = now[0];
				int nowJ = now[1];
				if(group[nowI][nowJ]!=0) continue; // 이미 그룹이 있음
				group[nowI][nowJ] = groupNum;
				visitCount++;
				for(int k=0;k<4;k++) {
					int nextI = nowI + nextDir[k][0];
					int nextJ = nowJ + nextDir[k][1];
					if(nextI < 0 || nextI >=N || nextJ <0 || nextJ >=M) continue;
					if(group[nextI][nextJ]!=0) continue; // 탐색할 칸이 이미 그룹이 있음
					if(map[nextI][nextJ]==0) { // 그룹없는 빈칸
						q.add(new int[] {nextI,nextJ});
					}
				}
			}
			return visitCount;
		}
		public static int getResult(int i,int j) {
			if(map[i][j]==0) return 0;
			HashSet<Integer> visitGroup = new HashSet<>(); // 그룹중복방지용 
			int visitCount = 1; // 벽을 부수므로 1
			for(int k=0;k<4;k++) { // 사방 4칸의 그룹의 갈수있는 칸 수 더하기
				int nextI = i + nextDir[k][0];
				int nextJ = j + nextDir[k][1];
				if(nextI < 0 || nextI >=N || nextJ <0 || nextJ >=M) continue;
				if(map[nextI][nextJ]==0 && !visitGroup.contains(group[nextI][nextJ])) {
					visitGroup.add(group[nextI][nextJ]); // 방문한 그룹 체크
					visitCount += groupMemberCount.get(group[nextI][nextJ]); // 해당그룹의 칸 수
				}
			}
			return visitCount%10;
		}
}

Set을 사용해서 방문한 그룹을 체크해서 중복되는 경우를 없앴다.

'개발 > 알고리즘' 카테고리의 다른 글

백준 16234 인구 이동  (1) 2022.06.14
백준 1865번 웜홀  (0) 2022.06.04
백준 12851번 숨바꼭질2  (0) 2021.06.22
백준 1937번 욕심쟁이 판다  (0) 2021.06.20
백준 1956번 운동  (0) 2021.06.18

'개발/알고리즘'의 다른글

  • 현재글백준 16946번 벽 부수고 이동하기4

관련글

티스토리툴바