인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요 교수님

교수님께서 알려주신 8-15번 풀이를 적용하여

추가문제 백준 17141 연구소 2를 풀고 있습니다

그런데 어떻게 풀어도 계속 메모리 초과가 나서 뭐가 문젠지 모르겠습니다...

import java.util.*;

class Pointo{

int y; int x;

Pointo(int y, int x){

this.y=y;

this.x=x;

}

}

public class Main {

static int n;

static int m;

static int[][] arr;

static int[] pm;

static int[] dx= {0,0,+1,-1};

static int[] dy= {+1,-1,0,0};

static ArrayList<Pointo> list=new ArrayList<>();

static int answer=Integer.MIN_VALUE;

public static void main(String[] args) {

Scanner scanner=new Scanner(System.in);

n=scanner.nextInt();

m=scanner.nextInt();

arr=new int[n][n];

pm=new int[m];

for(int i=0; i<n; i++) {

for(int j=0; j<n; j++) {

arr[i][j]=scanner.nextInt();

if(arr[i][j]==2) {

list.add(new Pointo(i,j));

}

}

}

dfs(0,0);

if(answer!=0)System.out.println(answer);

else System.out.println("-1");

}

public static void dfs(int val, int next) {

if(val==m) {

bfs(0);

return;

}

else {

for(int i=next; i<list.size(); i++) { //list에서 m개뽑자

pm[val]=i;

dfs(val+1,i+1);

}

}

}

public static void bfs(int val) {

int[][] copyarr=new int[n][n];

int[][] dis=new int[n][n];

Queue<Pointo> q=new LinkedList<>();

for(int i=0; i<pm.length; i++) {

int l=pm[i];

int qx=list.get(l).x;

int qy=list.get(l).y;

q.add(new Pointo(qy,qx));

copyarr[qy][qx]=2;

}

//copyarr 벽 만들기

for(int i=0; i<n; i++) {

for(int j=0; j<n; j++) {

if(arr[i][j]==1) {

copyarr[i][j]=1;

}

}

}

while(!q.isEmpty()) {

Pointo p=q.poll();

for(int i=0; i<4; i++) {

int nx=p.x+dx[i];

int ny=p.y+dy[i];

if(nx>=0 && ny>=0 && nx<n && ny<n) {

if(copyarr[ny][nx]!=1) {

copyarr[ny][nx]=2;

dis[ny][nx]=dis[p.y][p.x]+1;

q.add(new Pointo(ny,nx));

}

}

}

}

count(copyarr,dis);

}

public static void count(int[][] arr, int[][] dis) {

int maxy=0;

for(int i=0; i<n; i++) {

for(int j=0; j<n; j++) {

if(dis[i][j]>maxy)

maxy=dis[i][j];

}

}

answer=Math.max(maxy,answer);

}

}