8일차를 보니 벌써 2주나 쉬었다. 그동안 몸살이나, 스터디 활동이 원활하지 않아, 나태해졌던 것 같다!
다시 한번 시작하자.
1. 백준 2164 카드2
아이디어
- 처음에는 Stack으로 구현하였으나, 맨 아래로 넣는 작업에서 FIFO인 Queue로 구현하는것이 맞음.
- 맨 앞에서 빼기: poll() / 맨 뒤에 추가하기 : offer (), add()
- 구현 클래스는 LinkedList가 구현한다.
package boj_silver.p2164_카드2;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//스택
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Queue<Integer> q = new LinkedList<>();
//q에 1부터 ,,N까지 넣기
for(int i = 1; i<=n; i++){
q.offer(i);
}
//
while(true){
//큐에 있는 개수가 1이 될때 poll하기 -> break
if (q.size() ==1){
int num = q.poll();
System.out.println(num);
break;
}//if
//맨 첫번째 빼기
q.poll();
//맨 위에 있는것 맨 뒤로 보내기
q.offer(q.poll());
}
scan.close();
}
}
2. 백준 2178 미로탐색
아이디어
- map[n][m] 배열에 거리를 담자! (map[nx][ny] = map[cx][cy] + 1)
- 주의! 범위 체크! map[nx][ny] ==1 인것만 탐색
1. bfs로 풀기
package boj_silver.p2178_미로탐색;
import java.util.*;
import java.io.*;
public class Review4 {
static int n,m;
static int[][] map;
static boolean[][] visited;
static int[] dx ={-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
//1,1에서 출발하여, N, M의 위치로 갈때 지나야하는 최소 칸의 개수
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
n = scan.nextInt(); m = scan.nextInt();
scan.nextLine();
map= new int[n+1][m+1];
visited = new boolean[n+1][m+1];
for (int i= 1; i<=n;i++){
String line = scan.nextLine();
for (int j =1; j<=m;j++){
map[i][j] = line.charAt(j-1)-'0';
}
}//for
// System.out.println(Arrays.deepToString(map));
bfs(1,1);
System.out.println(map[n][m]);
}
static void bfs(int x, int y){
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{x,y});
visited[x][y] = true;
while (!q.isEmpty()){
int[] cur = q.poll();
int cx= cur[0];
int cy= cur[1];
//4방향 탐색
for (int i = 0; i<4; i++){
int nx = cx+dx[i];
int ny = cy+dy[i];
//범위 조건: 가장 자리 조건
if(nx>0 && ny>0 && nx<=n && ny<=m){
//범위 조건: 탐색하지 않은것, 배열안이 1인것만 탐색
if(!visited[nx][ny] && map[nx][ny] ==1){
visited[nx][ny] = true;
q.offer(new int[]{nx,ny});
map[nx][ny] = map[cx][cy] +1;
}
}
}
}
}
}
2. dfs로 풀기
static void main(String[] args){
visited[1][1]= true;
System.out.println(minDistance);
}//main
static void dfs(int x, int y, int distance){
//도착
if (x==n && y==m){
minDistance = Math.min(minDistance, distance);
return;
}
//탐색
for (int i = 0; i<4; i++){
int nx = x+dx[i];
int ny = y+ dy[i];
if (nx>0 && nx<=n && ny>0 && ny<=m){
if (!visited[nx][ny] && map[nx][ny] ==1){
visited[nx][ny]= true;
dfs(nx, ny, distance+1);
visited[nx][ny] = false; //백트래킹
}
}
}
}
3. 백준 1260 dfs와 bfs
아이디어
LinkedList<Integer>[] list배열로 받기- 간선 입력 받고, 정렬하기 (Collections.sort(list[i]))
- dfs -> bfs로 바꿀때, visited 초기화
- dfs) 현재 정점 방문 처리-> 출력 -> 인접 정점 탐색 (재귀)
- bfs) Queue 선언 -> Q offer -> q가 빌때까지 인접 정점 출력
package boj_silver.p1260_dfs와bfs;
import java.io.*;
import java.util.*;
public class Review1 {
static int V;
static boolean[] visited;
static LinkedList<Integer>[] list;
//정점 번호가 작은 것 먼저 방문, 더 이상 방문 x-> 종료
public static void main(String[] args) throws IOException {
//Linked List<Integer>[] 로 하고, 우선순위 큐
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
//n개 생성
list = new LinkedList[N+1];
//모든 리스트 초기화
for (int i = 1; i<=N; i++){
list[i] = new LinkedList<>();
}
//M개 입력 받기
for (int i = 1; i<= M; i++){
st = new StringTokenizer(br.readLine());
//list 초기화 하기
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
//양방향 입력-> 정렬하기 작은 것 부터 방문해야한다.
list[a].add(b);
list[b].add(a);
}
//정렬하기
for (int i = 1; i<=N; i++){
Collections.sort(list[i]); //모두 정렬하기
}
//첫번째 dfs
visited = new boolean[N+1];
dfs(V);
System.out.println();
visited = new boolean[N+1];
bfs(V);
}
static void dfs(int v){
//현재 정점 방문 처리 -> 현재 정점 출력
visited[v] = true;
System.out.print(v + " ");
//인접 정점 탐색 -> 방문 안한 정점 재귀 호출
// list[v]의 인점 정점 돌면서
for (int next: list[v]){
if(!visited[next]){
dfs(next); // 재귀
}
}//
}
static void bfs(int v){
Queue<Integer> q = new ArrayDeque<>();
q.offer(v);
visited[v] = true;
while(!q.isEmpty()){
int cur = q.poll();
System.out.print(cur + " ");
//인접 정점
for (int next: list[cur]){
if(!visited[next]){
q.offer(next);
visited[next] = true;
}
}
}
}
}
4. 백준 1012 유기농 배추
아이디어
1. 배추 있는 좌표 리스트에 {y,x}순으로 저장함.
package boj_silver.p1012유기농배추;
//몇개의 bfs가 호출되는지 !
import java.io.*;
import java.util.*;
public class Main {
static boolean[][] visited;
static int m,n;
static int[][] map;
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { 1, 0, -1, 0 };
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
int T = Integer.parseInt(bf.readLine());
for (int i = 0; i < T; i++) {
st = new StringTokenizer(bf.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());//배추의 개수
ArrayList<int[]> list = new ArrayList<>();
map = new int[n][m];
visited = new boolean[n][m]; //초기화
//k의 줄에 배추의 위치가 저장
for (int j = 0; j< k; j++){
st = new StringTokenizer(bf.readLine());
int x = Integer.parseInt(st.nextToken()); //가로 좌표
int y = Integer.parseInt(st.nextToken());//세로 좌표
list.add(new int[]{y,x});
map[y][x] = 1;
}// list에 있는 것 돌면서 !
//boolean[] listVisited = new boolean[list.size()];
int sum = 0;
for (int[] cur: list){
if (!visited[cur[0]][cur[1]]){
bfs(cur[0], cur[1]);
sum++;
}
}
System.out.println(sum);
}
bf.close();
}//main
static void bfs(int x, int y){
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{x,y});
visited[x][y] = true;
while(!q.isEmpty()){
int [] cur = q.poll();
int cx = cur[0];
int cy = cur[1];
for (int i = 0; i < 4; i++) {
int nx = cx+ dx[i];
int ny = cy+ dy[i];
if (nx>=0 && nx<n && ny>=0 && ny<m){
if(!visited[nx][ny] && map[nx][ny]==1 ) {
q.offer(new int[]{nx,ny});
visited[nx][ny] = true;
}
}
}//for
}
}
}
2. 리스트 없이 2중 for문
아이디어
1번
입력받을때 리스트에 좌표를 저장한다. (가로, 세로)로 주어짐 -> list.add(new int[] {y,x}) 로 저장
map[y][x] = 1;
-> 리스트에 있는 배추만 확인
2번: 2중 for문
입력받을때 map에만 저장한다. map[y][x] = 1;
전체 map을 순회하면서 배추를 찾는다.
==> 둘다 괜찮으나, 리스트를 사용하는 경우는, K가 훨씬 작을때 사용하고, 2중 for문은 코드 간결성과 K가 nxm에 가까울때
//map 전체를 돌면서,
package boj_silver.p1012유기농배추;
//몇개의 bfs가 호출되는지 !
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_effi {
static boolean[][] visited;
static int m,n;
static int[][] map;
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { 1, 0, -1, 0 };
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
int T = Integer.parseInt(bf.readLine());
for (int i = 0; i < T; i++) {
st = new StringTokenizer(bf.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());//배추의 개수
//ArrayList<int[]> list = new ArrayList<>();
map = new int[n][m];
visited = new boolean[n][m]; //초기화
//k의 줄에 배추의 위치가 저장
for (int j = 0; j< k; j++){
st = new StringTokenizer(bf.readLine());
int x = Integer.parseInt(st.nextToken()); //가로 좌표
int y = Integer.parseInt(st.nextToken());//세로 좌표
//list.add(new int[]{y,x});
map[y][x] = 1;
}// list에 있는 것 돌면서 !
//boolean[] listVisited = new boolean[list.size()];
//전체 맵 탐색
int cnt =0;
for (int x =0; x<n;x++){
for (int y =0; y<m;y++){
if(map[x][y] ==1 && !visited[x][y]){
bfs(x,y);
cnt++;
}
}
}
System.out.println(cnt);
// int sum = 0;
// for (int[] cur: list){
// if (!visited[cur[0]][cur[1]]){
// bfs(cur[0], cur[1]);
// sum++;
// }
//
// }
// System.out.println(sum);
}
bf.close();
}//main
static void bfs(int x, int y){
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{x,y});
visited[x][y] = true;
while(!q.isEmpty()){
int [] cur = q.poll();
int cx = cur[0];
int cy = cur[1];
for (int i = 0; i < 4; i++) {
int nx = cx+ dx[i];
int ny = cy+ dy[i];
if (nx>=0 && nx<n && ny>=0 && ny<m){
if(!visited[nx][ny] && map[nx][ny]==1 ) {
q.offer(new int[]{nx,ny});
visited[nx][ny] = true;
}
}
}//for
}
}
}
따뜻한 시선으로 세상을 변화시키는 데이터사이언티스트