Leetcode 317) Shortes Distance from All Buildings
in Algorithms
내 답안
- 코드가 치덕치덕하다. 슬프다.
- 헉하고 어려운 느낌은 안들었는데 많이 틀리ㅁ..
- 빌딩이 있는 부분들을 먼저 시작.
- visited 어레이를 여러개 만들어줬는데, 그러지 말고 하나에 다 넣어서 빌딩 cnt랑 같으면 ok이런식으로 해도 됐을거같다.
- 코드에서 position 이차원 어레이가 블로그 빌드할 때 페일해서 주석처리 해놓음.
class Solution {
public int shortestDistance(int[][] grid) {
//q만들기
Queue<int[]> q =new LinkedList<>();
//visited 1이면 방문, 0이면 안 방문
int[][] position = {{-1,0},{1,0},{0,-1},{0,1}};
//10씩 더해서 나중에 답은 나누자..!
List<int[][]> visitInfo =new ArrayList<>();
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]==1){
int[][] visited = new int[grid.length][grid[0].length];
visitInfo.add(visited);
q.add(new int[]{i,j});
int add =0;
while(!q.isEmpty()){
int size=q.size();
add+=10;
for(int s =0;s<size;s++){
int[] cur = q.poll();
visited[cur[0]][cur[1]]=1;
for(int[] ind : position){
int a = cur[0]+ind[0];
int b = cur[1]+ind[1];
if((a <grid.length) && (a>=0) &&(b<grid[0].length) && (b>=0)){
if (visited[a][b]==0){
if(grid[a][b]!=1 && grid[a][b]!=2 ){
grid[a][b]+=add;
q.add(new int[]{a,b});}
visited[a][b]=1;
}
}
}
}
}
}
}
}
int res= Integer.MAX_VALUE;
int visitSize = visitInfo.size();
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
grid[i][j]/=10;
if(grid[i][j]>0 && res>grid[i][j]){
boolean ok = true;
for(int z =0;z<visitSize;z++){
if(visitInfo.get(z)[i][j]!=1){
ok=false;
}
}
if(ok){
res=grid[i][j];
}
}
}
}
if(res==Integer.MAX_VALUE){
res= -1;
}
return res;
}
}
visited를 숫자로 count해도 성능이 어쨌든 비슷하다. 그게 time complexity에 미치는 영향이 적어서 그렇겠지..
```java class Solution { public int shortestDistance(int[][] grid) {
//q만들기 Queue<int[]> q =new LinkedList<>(); //visited 1이면 방문, 0이면 안 방문int[][] position = {{-1,0},{1,0},{0,-1},{0,1}}; //10씩 더해서 나중에 답은 나누자..! List<int[][]> visitInfo =new ArrayList<>(); for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(grid[i][j]==1){ int[][] visited = new int[grid.length][grid[0].length]; visitInfo.add(visited); q.add(new int[]{i,j}); int add =0; while(!q.isEmpty()){ int size=q.size(); add+=10; for(int s =0;s<size;s++){ int[] cur = q.poll(); visited[cur[0]][cur[1]]=1; for(int[] ind : position){ int a = cur[0]+ind[0]; int b = cur[1]+ind[1]; if((a <grid.length) && (a>=0) &&(b<grid[0].length) && (b>=0)){ if (visited[a][b]==0){ if(grid[a][b]!=1 && grid[a][b]!=2 ){ grid[a][b]+=add; q.add(new int[]{a,b});} visited[a][b]=1; } } } } } } } } int res= Integer.MAX_VALUE; int visitSize = visitInfo.size(); for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ grid[i][j]/=10; if(grid[i][j]>0 && res>grid[i][j]){ boolean ok = true; for(int z =0;z<visitSize;z++){ if(visitInfo.get(z)[i][j]!=1){ ok=false; } } if(ok){ res=grid[i][j]; } } } } if(res==Integer.MAX_VALUE){ res= -1; } return res; } }
다른 답안
class Solution {
final static int[] d = {0, 1, 0, -1, 0};
int min = Integer.MAX_VALUE;
public int shortestDistance(int[][] grid) {
int[][] dist = new int[grid.length][grid[0].length];
int cur = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
helper (grid, dist, i, j, cur--);
}
}
}
return min == Integer.MAX_VALUE ? -1 : min;
}
void helper (int[][] grid, int[][] dist, int row, int col, int mark) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{row, col});
min = Integer.MAX_VALUE;
int dis = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int l = 0; l < size; l++) {
int[] cur = queue.remove();
for (int k = 0; k < 4; k++) {
int x = cur[0] + d[k];
int y = cur[1] + d[k + 1];
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == mark) {
dist[x][y] += dis;
min = Math.min(min, dist[x][y]);
grid[x][y] = mark - 1;
queue.offer(new int[]{x, y});
}
}
}
dis++;
}
}
}
오답
- 세 건물을 다 visit했다는 증표가 필요한데, 이 코드에서는 그걸 찾기가 어렵다.
class Solution {
public int shortestDistance(int[][] grid) {
//q만들기
Queue<int[]> q =new LinkedList<>();
//visited 1이면 방문, 0이면 안 방문
int[][] position = {{-1,0},{1,0},{0,-1},{0,1}};
//10씩 더해서 나중에 답은 나누자..!
int buildings =0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]==1){
buildings++;
int[][] visited = new int[grid.length][grid[0].length];
q.add(new int[]{i,j});
int add =0;
while(!q.isEmpty()){
int size=q.size();
add+=10;
for(int s =0;s<size;s++){
int[] cur = q.poll();
visited[cur[0]][cur[1]]=1;
for(int[] ind : position){
int a = cur[0]+ind[0];
int b = cur[1]+ind[1];
if((a <grid.length) && (a>=0) &&(b<grid[0].length) && (b>=0)){
if (visited[a][b]==0){
if(grid[a][b]!=1 && grid[a][b]!=2 ){
grid[a][b]+=add;
q.add(new int[]{a,b});}
visited[a][b]=1;
}
}
}
}
}
}
}
}
int res= Integer.MAX_VALUE;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
grid[i][j]/=10;
//오답노트 정리
if(grid[i][j]>= buildings&&res>grid[i][j]){
res=grid[i][j];
}
}
}
if(res==Integer.MAX_VALUE){
res= -1;
}
return res;
}
}
