백준 2667 : 단지번호 붙이기 (★다시풀어보기!!)
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static int dx[]= {0,0,1,-1}; //(x,y) 1. 오른쪽으로 한칸 , 2. 왼쪽으로한칸, 3. 아래로 한칸, 4. 위로 한칸
public static int dy[]= {1,-1,0,0};
static int n,m,v;
static int[][] arr;
static int cnt;
static int[] dan=new int[25*25];
static int[][] visited;
public static void main(String[] args) {
n=scan.nextInt();
arr=new int[n][n];
visited=new int[n][n];
for(int i=0;i<n;i++) { //입력
String str = scan.next();
for(int j=0;j<n;j++){
arr[i][j]=str.charAt(j)-'0';
}
}
for(int a=0;a<n;a++) {
for(int b=0;b<n;b++){
if(arr[a][b]==1&&visited[a][b]==0) { //if문 한번 만족할때마다 한단지
cnt++;
dfs(a,b);
}
}
}
System.out.println("총단지 수"+cnt);//총단지수
Arrays.sort(dan);
System.out.println("test"+dan.length);//총단지수
for(int k=0;k<dan.length;k++) {
if(dan[k]==0) {}
else {
System.out.println(dan[k]);}
}
//출력 총단지수, 단지 내 집 수 차례로 (ln)
}
public static void dfs(int i,int j) {
visited[i][j]=1;
dan[cnt]++; //단지 아파트 개수 ++해주기
//기본 dfs 에서는 for 문으로 n까지 돌면서 -> 다음 노드를 찾는 거였는데
//이번 문제에서는 0인 부분을 마지막으로 탐색을 해야하기때문에 십자가 모양으로 탐색
for(int k=0;k<4;k++) {
int nx=i+dx[k];
int ny=j+dy[k];
//배열을 뚫고 나갈때는 제외하기 왼쪽 벽 윗벽 = 0, 오른쪽벽 아래벽= n
if(nx>=0&&ny>=0&&nx<n&&ny<n) {
if(arr[nx][ny]==1&&visited[nx][ny]==0) {// 아파트가 있고 방문하지 않았으면
dfs(nx,ny);
}
}
}
}
}실수 포인트
코드를 다짜고 0000 밖에 출력되지않아서 원인을 찾아봤더니 입력되는 보드 배열이 띄어쓰기 없이 주어졌기 때문에 한줄씩 문자열로 받고 charat으로 한글자씩 배열에 넣어줘야했다. 디버깅을 해보았을 때 계속 배열 비교가 안되서 디버깅자체가 오류인가..? 체크포인트가 적용이 안되는건가 했는데 charAt을 사용해서 문자형으로 저장된것을 정수비교하려니 다 비교가 안되어 모든값이 0이 된것이였다...!!저번에 풀었던 문제에서는 해당 문자를 정수로서 처리하지 않아도 되었기 때문에 괜찮았지만 이번에는 -'0'을 해주어 정수형으로 변경했다. -'0'을 해줘야하는 이유는 여기에서 =>문자형을 정수형으로 바꾸기
그리고 dan 배열의 index값이 cnt: 단지 개수 세린 값인데 왜 출력값이
총단지 수3
test625
622번째7
623번째8
624번째9
이렇게 나오는지는 의문이다 ㅠㅠ
백준 13023 : ABCDE
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static int dx[]= {0,0,1,-1}; //(x,y) 1. 오른쪽으로 한칸 , 2. 왼쪽으로한칸, 3. 아래로 한칸, 4. 위로 한칸
public static int dy[]= {1,-1,0,0};
static int n,m,v;
static int[][] arr,arr2;
static int cnt,cnt2=0;
static int[] dan=new int[25*25];
static boolean[] visited;
static ArrayList<Integer>[] list;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
visited=new boolean[n];
list=new ArrayList[n];
for(int i = 0; i < n; i++) {
list[i] = new ArrayList<Integer>();
}
for(int i=0;i<m;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
list[a].add(b);
list[b].add(a);
}
for(int i=0;i<n;i++) {// n까지 방문하지 않은 노드 방문
if(cnt2==0) {
dfs(i,1);
}
}
System.out.print(cnt2);
}
public static void dfs(int i,int cnt) {
if(cnt==5) {
cnt2=1;
return;
}
visited[i]=true;
//방문했다고 표시
//인접 노드 찾기
for(int k:list[i]) { //인접리스트에 포함된 값
if(visited[k]==false) {
dfs(k,cnt+1);
}
}
visited[i]=false;
}
}실수 포인트
- 처음에는 탐색을 할 때 DEPTH가 5인지 아닌지 판단을 하면 답이 나온다고 생각했다
-> - 근데 예제 3을 보니까 다시 0으로 돌아와서 탐색하는 경우가 있어서 아니라고 생각
-> 3. 블로그를 찾아보다보니까 DEPTH가 5 찾는게 맞았고 0으로 돌아오는 경우는 DEPTH가 2까지 밖에 탐색이 안되는 것이였다.
여기서 cnt 변수를 만들어 주고 dfs 함수에 진입할때마다 ++해줬는데 맨 끝 depth까지 진입해도 cnt가 초기화 되지 않기때문에 함수에 인자로 전달해줬다. - 하지만 맨처음에 탐색을 시작하는 0이 그래프의 중심에 있을 때 탐색의 depth가 한쪽에 있는 노드들만 탐색한 만큼밖에 카운트 되지 않기때문에 visited 를 false로 바꿔줘야했다
- 그리고 드디어 인접배열로는 시간초과가 뜨는 문제를 만났다..
인접배열을 사용하여 문제를 풀었다.
ArrayList 사용방법을 정리
ArrayList는 배열과 다르게 크기가 가변적으로 변한다. 그래서 복잡도를 줄일수 있다.
우리는 이차원으로 써야하니까 배열로 생성해주거나
ArrayList[] list= new list[n];
for(int i = 0; i < n; i++) {
list[i] = new ArrayList();
}
이런식으로 arraylist in arraylist로 만들어준다. 객체 생성은 n개를 for문을 사용해서 각각 해야한다.
ArrayList<ArrayList> list =new ArrayList<>();
for(int i=0;i<n; i++) {
list.add(new ArrayList<>());
}
한가지 방법을 외워서 쓰자~
백준 2606 : 바이러스
package codeup100;
import java.util.*;
public class Main {
static Scanner scan=new Scanner(System.in);
static ArrayList<ArrayList<Integer>> list =new ArrayList<>();
static int[] visited;
static int cnt;
public static void main(String[] args) {
int n=scan.nextInt();
int m=scan.nextInt();
visited=new int[n+1];
for(int i=0;i<n+1;i++) {
list.add(new ArrayList<>());
}
for(int i=0;i<m;i++) { //arraylist에 연결된 노드 기록
int a=scan.nextInt();
int b=scan.nextInt();
list.get(a).add(b);
list.get(b).add(a);
}
dfs(1);
for(int i=0;i<n+1;i++) {
if(visited[i]==1) {
cnt++;
}
}
System.out.println(cnt-1);
}
static void dfs(int i) {
visited[i]=1;
for(int m:list.get(i)) {
if(visited[m]==0) {
dfs(m);
}
}
}
} dfs의 개념만 잘 알면 쉽게 풀수있는 문제!
연결리스트 선언하고 get이랑 add로 인접리스트 만들수있으면 다시 풀지 않아도 될것같다.
백준 11725 : 트리의 부모찾기
import java.util.*;
public class Main {
static Scanner scan=new Scanner(System.in);
static ArrayList<ArrayList<Integer>> list =new ArrayList<>();
static int[] visited;
static int[] parent;
static int cnt;
public static void main(String[] args) {
int n=scan.nextInt();
visited=new int[n+1];
parent=new int[n+1];
for(int i=0;i<n+1;i++) {
list.add(new ArrayList<>());
}
for(int i=0;i<n-1;i++) { //arraylist에 연결된 노드 기록
int a=scan.nextInt();
int b=scan.nextInt();
list.get(a).add(b);
list.get(b).add(a);
}
for(int k=1;k<n+1;k++) {
if(visited[k]==0) {
dfs(k);
}
}
for(int i=2;i<n+1;i++) {
System.out.println(parent[i]);
}
}
static void dfs(int i) {
visited[i]=1;
for(int m:list.get(i)) {
if(visited[m]==0) {
parent[m]=i;
dfs(m);
}
}
}
}문제를 이해 못해서 블로그를 찾아봤다! 1을 최상위 노드로 놓고 2부터 n-1까지 각각의 부모노드를 출력하라는 말이였다!!ㅋㅋ 위에서 적어놓은 dfs코드에 한줄 추가해서 쉽게 풀수있었다!
백준 1325 : 효율적인 해킹
package codeup100;
import java.util.*;
public class Main {
static Scanner scan=new Scanner(System.in);
static ArrayList<ArrayList<Integer>> list =new ArrayList<>();
static int[] visited;
static int[] ans;
static int cnt;
public static void main(String[] args) {
int n=scan.nextInt();
int m=scan.nextInt();
ans=new int[n+1];
for(int i=0;i<n+1;i++) {
list.add(new ArrayList<>());
}
for(int i=0;i<m;i++) { //arraylist에 연결된 노드 기록
int a=scan.nextInt();
int b=scan.nextInt();
list.get(b).add(a);
}
int max=0;
for(int k=1;k<n+1;k++) {
cnt=0;
visited=new int[n+1];
dfs(k,k);
max=Math.max(ans[k], max);
}
StringBuilder sb=new StringBuilder();
for(int i=1;i<n+1;i++) {
if(ans[i]==max) {
sb.append(i+" ");
}
}
System.out.println(sb.toString());
}
static void dfs(int i,int start) {
visited[i]=1;
for(int m:list.get(i)) {
if(visited[m]==0) {
dfs(m,start);
ans[start]++;
}
}
}
}탐색횟수가 가장 많은 노드에서 시작하는 것이 최대로 많이 해킹할 수 있는 것이므로 b리스트 원소에 a를 넣어주고 각각 노드로 시작하면서 최대 탐색횟수를 찾았다. 테스트케이스를 넣었을 때 정답이 나오는데 시간초과가 뜬다. 테스트케이스가 너무 적고 문제자체가 시간이 타이트해서 같은 코드라도 될때도 있고 안될때도 있다고 한다.
참고블로그
이블로그 코드를 보면 a->b로해서 전부의 노드에서 탐색을 시작하는데 cnt라는 배열에 각 노드가 도착한 횟수를 저장하는데 내가 생각한것이랑은 완전 반대로 도착한 횟수가 가장많으면 그 노드에서 시작했을 때 도달할 수 있는 컴퓨터가 가장 많다고 풀이했다. 근데 시간복잡도상에서 차이가 크게 나는지 모르겠다 ㅠㅠㅠㅠ.... 내일 한번 검사해봐야지 다시풀필요 x
