Writer: Steven, Lee
Date: 4/8, Monday
Purpose: Solving Replace O's with X's
Topic: Graph, Matrix, Recursion
Level: Medium
Percentage: 20.83% have solved this problem
Time: it took me 30 minutes :)
Time Complexity: O(n^2) worst case
Runtime: 11 ms
한국어 버전은 밑에 있습니다.
* Caution * Before you read the solution that I used, you need to solve this problem by yourself
* Description *
Given a matrix of size N x M where every element is either ‘O’ or ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’. A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.
Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two integers N and M denoting the size of the matrix. Then in the next line are N\M space separated values of the matrix.
Output: For each test case print the space separated values of the new matrix.
Constraints:
1<=T<=10
1<=mat[][]<=100
1<=n,m<=20
* Example *
#1 Ex)
Input: mat[N][M] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'O', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Output: mat[N][M] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X', 'X', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Input: mat[N][M] = {{'X', 'X', 'X', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'O', 'O', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};
Input: mat[N][M] = {{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};#2 Ex) $ You need to print out this format $
Input:
2
1 5
X O X O X
3 3
X X X X O X X X X
Output:
X O X O X
X X X X X X X X X
* Idea*
The main point of this problem is that 'O' will be replaced with 'X' if it's surrounded by 'X' at locations just left, right, above, below of it. You can easily find out that it doesn't replace at all if N or M of a matrix is below 3. There is the only way to convert it when 'X' at left, right, above, below of the target exists. so if a given mat is satisfied that condition (below 3) it just print out it. Next, what if it's not satisfied it (more than 3), then we are going to traverse every edge of horizontal and vertical and if there is a 'O' and it's not visited yet at the position. we need to connect it with every adjacent 'O's and it's not visited. ( we have to mark it as visited all the time ) After finishing the process, we are going to traverse the mat again from (1,1). if there is a 'O' and it's not visited, we need to replace it with 'X' Because it's satisfied the surrounded condition. Let me give u more details about it with an example.
Here is the example
X X O X X F F F F F
X X O X X F F F F F
X O X O X <= Matrix F F F F F <= Visited Map
X O X O X <= M: 5, N: 5 F F F F F <= M: 5, N: 5
X O X X X F F F F F
1. Traverse every edges of it and if there is a 'O' and it's not visited yet, we have to start here
* We must mark it as True !! *
X X O X X F F T F F * map[0][2] is true now
X X O X X F F F F F
X O X O X F F F F F
X O X O X F F F F F
X O X X X F T F F F * map[4][1] is true now
2. We have to connect with every adjacent 'O's and it's not visited from the target
* We must mark it as True*
X X O X X F F T F F * map[0][2] is true
X X O X X F F F F F * map[1][2] is true now
X O X O X F F F F F * map[2][1] is true now
X O X O X F F F F F * map[3][1] is true now
X O X X X F T F F F * map[4][1] is true
3. Finally, we traverse it again, if there is a 'O' and it's not visited, we need to replace it with 'X'
X X O X X F F T F F * map[0][2] is true
X X O X X F F F F F * map[1][2] is true now
X O X X X * mat[2][3] is 'X' F F F F F * map[2][1] is true now
X O X X X * mat[3][3] is 'X' F F F F F * map[3][1] is true now
X O X X X F T F F F * map[4][1] is true
4. Print it out
(한국어)
* 난이도: 중간 *
* 오직 20.83%만이 이 문제를 풀었습니다. *
* 저는 30분 정도가 걸렸습니다. *
* 시간 복잡도는 O(n^2)입니다 *
* 런타임은 11ms입니다. *
* 주의 * 솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.
* 지문 *
크기가 N x M인 행렬이 주어집니다. 여기의 모든 요소들은 'O' 아니면 'X'로 되어 있습니다. 만약 주위가 'X'로 둘러싸여 있으면 'O'를 'X'로 교체하세요. 만약 'X'가 그 'O'의 위쪽, 아래쪽, 왼쪽, 오른쪽에 있으면 'O'는 'X'에 둘러싸여 있다라고 할 수 있습니다.
입력: 첫 번째 줄에 들어오는 T는 테스트의 수를 의미합니다. 그리고 각 테스트의 첫 째 줄은 행렬의 사이즈인 N과 M를 나타냅니다. 바로 그 다음 줄은 공백으로 분리되어 있는 N x M의 행렬의 값들을 의미합니다.
출력: 각 테스트마다 새로운 행렬의 값들을 공백으로 분리되게 출력을 합니다.
제한:
1<=T<=10
1<=mat[][]<=100
1<=n,m<=20
* 예시 *
#1 Ex)
Input: mat[N][M] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'O', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Output: mat[N][M] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X', 'X', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Input: mat[N][M] = {{'X', 'X', 'X', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'O', 'O', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};
Input: mat[N][M] = {{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};#2 Ex) $ 이런 형태로 출력을 해야 합니다. $
Input:
2
1 5
X O X O X
3 3
X X X X O X X X X
Output:
X O X O X
X X X X X X X X X
* 아이디어 *
이 문제의 가장 주요한 포인트는 'O'의 위치에서 상하좌우가 'X'일 때, 'O'는 'X'로 교체합니다. 여기서 쉽게 N 또는 M이 3보다 작을 때는 아무것도 바뀌지 않는 것을 알 수 있습니다. 오직 목표의 상하좌우의 위치에 'X'가 존재할 때만 교체가 발생합니다. 그래서 주어진 행렬이 저 조건( 3 보다 작음 )에 만족한다면 그냥 프린트하면 됩니다. 다음으로 만약 저 조건이 만족하지 않을 때 (3 보다 큼) 가로와 세로의 끝 부분을 순회합니다. 그리고 그 위치에서 'O'가 있고 아직 방문하지 않았다면 그 값과 인접한 모든 방문하지 않은 'O's들을 연결합니다. ( 매번 방문했다고 표시해야 합니다. ) 이 작업이 끝난 후에 (1, 1)부터 순회를 다시 합니다. 만약 방문하지 않은 'O'가 있다면 그것을 'X'로 바꿉니다. 왜냐하면 둘러싸인 조건에 충족하기 때문입니다. 이것을 예시와 함께 더 자세히 설명하겠습니다.
예시입니다.
X X O X X F F F F F
X X O X X F F F F F
X O X O X <= Matrix F F F F F <= Visited Map
X O X O X <= M: 5, N: 5 F F F F F <= M: 5, N: 5
X O X X X F F F F F
1. 모든 행렬의 끝 값들을 순회합니다. 그리고 만약 방문하지 않은 'O'가 있다면 그쪽부터 시작해야 합니다.
* 그 값이 True라고 표시해야 합니다. !! *
X X O X X F F T F F * map[0][2] is true now
X X O X X F F F F F
X O X O X F F F F F
X O X O X F F F F F
X O X X X F T F F F * map[4][1] is true now
2. 타겟으로부터 모든 근접한 방문하지 않은 'O'들을 연결해야 합니다.
* 그 값이 True라고 표시해야 합니다. !! *
X X O X X F F T F F * map[0][2] is true
X X O X X F F F F F * map[1][2] is true now
X O X O X F F F F F * map[2][1] is true now
X O X O X F F F F F * map[3][1] is true now
X O X X X F T F F F * map[4][1] is true
3. 마지막으로 한번 더 순회를 하고 방문하지 않은 'O'가 있으면 'X'로 교체합니다.
X X O X X F F T F F * map[0][2] is true
X X O X X F F F F F * map[1][2] is true now
X O X X X * mat[2][3] is 'X' F F F F F * map[2][1] is true now
X O X X X * mat[3][3] is 'X' F F F F F * map[3][1] is true now
X O X X X F T F F F * map[4][1] is true
4. 출력합니다.
* Check *
You can check it out here
이 사이트에서 정답의 유무를 확인하실 수 있습니다.
https://practice.geeksforgeeks.org/problems/replace-os-with-xs/0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | import java.util.*; public class ReplaceOsWithXs { public static void replaceOsWithXsHelp(char[][] map, boolean[][] visit){ for(int i = 0 ; i < map.length ; i++) { if(map[i][0] == 'O' && !visit[i][0]) replaceOsWithXsHelp(map, visit, i, 0); if(map[i][map[0].length-1] == 'O' && !visit[i][map[0].length-1]) replaceOsWithXsHelp(map, visit, i, map[0].length-1); } for(int j = 0 ; j < map[0].length ; j++) { if(map[0][j] == 'O' && !visit[0][j]) replaceOsWithXsHelp(map, visit, 0, j); if(map[map.length-1][j] == 'O' && !visit[map.length-1][j]) replaceOsWithXsHelp(map, visit, map.length-1, j); } return; } public static void replaceOsWithXsHelp(char[][] map, boolean[][] visit, int i , int j) { if(i < 0 || i >= map.length || j < 0 || j >= map[0].length || map[i][j] != 'O' || visit[i][j]) return; visit[i][j] = true; replaceOsWithXsHelp(map, visit, i-1, j); replaceOsWithXsHelp(map, visit, i+1, j); replaceOsWithXsHelp(map, visit, i, j-1); replaceOsWithXsHelp(map, visit, i, j+1); } public static void main(String[] args) { Scanner kb = new Scanner(System.in); int times = kb.nextInt(); for(int i = 0 ; i < times ; i++) { int col = kb.nextInt(); int row = kb.nextInt(); boolean flag = false; char[][] map = new char[col][row]; boolean[][] visit = new boolean[col][row]; kb.nextLine(); String temp = kb.nextLine().replaceAll(" ", ""); int start = 0, end = row; for(int j = 0 ; j < col ; j++) { map[j] = temp.substring(start, end).toCharArray(); start = end; end+=row; } if(col < 3 || row < 3) flag = true; else replaceOsWithXsHelp(map, visit); for(int x = 0 ; x < col ; x++) { for(int y = 0 ; y< row ; y++) { if(!flag && map[x][y] == 'O' && !visit[x][y]) map[x][y] = 'X'; System.out.print(map[x][y] + " "); } } System.out.println(); } } } | cs |
'DataStructures & Algorithm (Practice)' 카테고리의 다른 글
| Tree #2 Binary Tree to DLL (0) | 2019.04.13 |
|---|---|
| Tree #1 Count Number of SubTrees having given Sum (0) | 2019.04.10 |
| Google #4 Edit Distance (0) | 2019.04.04 |
| Google #3 Ugly Numbers (0) | 2019.04.03 |
| Google #2 Number of Islands (0) | 2019.01.27 |
