[ASAC 웹풀스텍 개발자과정] 03. 코딩테스트 백준 브론즈탈출을 목표로 간다(브4)
본문 바로가기

컴퓨터공부/ASAC 웹풀스택

[ASAC 웹풀스텍 개발자과정] 03. 코딩테스트 백준 브론즈탈출을 목표로 간다(브4)

by Life & study 2023. 7. 29.
반응형

개발일지 작성

[ASAC 웹풀스텍 개발자과정] 03. 코딩테스트 백준 브론즈탈출을 목표로 간다(브 4)

 

 

설리번 님의 개발일지

 

제목 작성일 속성 주차 공부내용 티스토리주소
[ASAC 웹풀스택 개발자과정] 03. 코딩테스트 백준 브론즈탈출을 목표로 간다 알고리즘웹 1주차 [백준 코딩테스트 문제] 11724번 연결요소의 개수 연결리스트 (DFS)문제 [백준 코딩테스트 문제] 2178번 미로찾기 큐 (BFS) 문제 [백준 코딩테스트 문제] js 내장함수 공부 [백준 코딩테스트 문제] 4963번 섬의 개수 (BFS) 문제 [백준 코딩테스트 문제] 2580번 스도쿠 문제 (BFS) 문제 https://comingsoon1004.tistory.com/entry/ASAC-웹풀스텍-개발자과정-03-코딩테스트-백준-브론즈탈출을-목표로-간다브4
[ASAC 웹풀스택 개발자과정] 02. 코딩테스트 백준 브론즈탈출을 목표로 간다 알고리즘웹 1주차 [백준 코딩테스트 문제 ] 9498번 시험 점수를 입력받아 90 ~ 100점은 A, 80 ~ 89점은 B, 70 ~ 79점은 C, 60 ~ 69점은 D, 나머지 점수는 F를 출력하는 프로그램을 작성하시오. [백준 코딩테스트 문제] 14681번 제n사분면 구하기. [백준 코딩테스트 문제] 자바스크립트 코드 백준 읽기 코드 [백준 코딩테스트 문제] 2753번 윤년구하기 [백준 코딩테스트 문제] 1712번 손익분기점 구하기 https://comingsoon1004.tistory.com/entry/ASAC-웹풀스택-개발자과정-02-코딩테스트-백준-브론즈탈출을-목표로-간다

 

  알고리즘웹
작성일
공부내용 [백준 코딩테스트 문제] 11724번 연결요소의 개수 연결리스트 (DFS)문제 [백준 코딩테스트 문제] 2178번 미로찾기 큐 (BFS) 문제 [백준 코딩테스트 문제] js 내장함수 공부 [백준 코딩테스트 문제] 4963번 섬의 개수 (BFS) 문제 [백준 코딩테스트 문제] 2580번 스도쿠 문제 (BFS) 문제
주차 1주차
티스토리주소 https://comingsoon1004.tistory.com/entry/ASAC-웹풀스텍-개발자과정-03-코딩테스트-백준-브론즈탈출을-목표로-간다브4

 

[백준 코딩테스트 문제] 11724번 연결요소의 개수 연결리스트 DFS 문제

 

[백준 코딩테스트 문제] 11724번 연결요소의 개수 연결리스트 DFS 문제


dfs는 Depth-First Search(깊이 우선 탐색)의 약자입니다.


시간제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
3초 512 MB 105181 47489 31335 42.245%

 

문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력
첫째 줄에 연결 요소의 개수를 출력한다.

 

const 버전 연결리스트 무방향

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

// 1. 정점 수와 간선 수 추출
const [v, line] = input[0].split(" ").map(Number);

// 2. 그래프 초기화
const graph = new Array(v + 1).fill(null).map(() => []);

// 3. 그래프에 간선 정보 추가
for (let i = 1; i <= line; i++) {
  const [node1, node2] = input[i].split(" ").map(Number);
  graph[node1].push(node2);
  graph[node2].push(node1);
}

function countConnectedLine(graph, v) {
  const visited = new Array(v + 1).fill(false);
  let count = 0;

  // 4. 깊이 우선 탐색 함수
  function dfs(vertex) {
    visited[vertex] = true;

    // 4.1 탐색하지 않은 인접 정점 관리
    for (const nextV of graph[vertex]) {
      if (!visited[nextV]) {
        dfs(nextV);
      }
    }
  }

  // 5. 연결 요소 카운트 및 dfs 호출
  for (let i = 1; i <= v; i++) {
    if (!visited[i]) {
      dfs(i);
      count++;
    }
  }

  return count;
}

// 6. 결과 출력
console.log(countConnectedLine(graph, v));

 

 

 

Function 버전 연결리스트 무방향

// 파일 시스템 모듈을 가져옵니다.
const fs = require("fs");
// 입력을 받아 문자열을 정리하고 배열로 변환합니다.
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

// 입력에서 정점 수와 간선 수를 추출합니다.
const { v, line } = vline(input);

// 그래프를 초기화합니다.
const graph = beginning(v);


// 주어진 입력에서 정점 수와 간선 수를 추출하는 함수
function vline(input) {
  const [v, line] = input[0].split(" ").map(Number);
  return { v: v, line: line };
}

// 주어진 정점 수로 그래프를 초기화하는 함수
function beginning(v) {
  const graph = new Array(v + 1).fill(null).map(() => []);
  return graph;
}


// 입력에서 간선 정보를 읽어 그래프에 추가합니다.
for (let i = 1; i <= line; i++) {
  const [node1, node2] = input[i].split(" ").map(Number);
  graph[node1].push(node2);
  graph[node2].push(node1);
}

// 그래프에서 연결 요소의 개수를 세는 함수
function countConnectedLine(graph, v) {
  const visited = new Array(v + 1).fill(false);
  let count = 0;



  // 깊이 우선 탐색 함수
  function dfs(vertex) {
    visited[vertex] = true;

    // 탐색하지 않은 인접 정점을 관리합니다 
    for (const nextV of graph[vertex]) {
      if (!visited[nextV]) {
        dfs(nextV);
      }
    }
  }

  // 연결 요소를 카운트하고 깊이 우선 탐색을 호출합니다.
  for (let i = 1; i <= v; i++) {
    if (!visited[i]) {
      dfs(i);
      count++;
    }
  }

  return count;
}

// 연결 요소의 개수를 출력합니다.
console.log(countConnectedLine(graph, v));

 

const graph = new Array(v + 1). fill(null). map(() => []);

 

이 코드는 그래프를 인접 리스트 형태로 구현하기 위해 필요한 작업입니다.
new Array(v + 1): 배열 인스턴스를 생성하고 길이를 (v + 1)로 설정합니다. 

 

여기서 v는 정점 수를 의미하며, 가독성을 높이고 배열 인덱스와 정점 번호를 일치시키기 위해 1을 더하여 길이를 설정합니다. 결과적으로 인덱스 0은 사용되지 않습니다.


fill(null): 배열의 모든 요소를 null로 채웁니다. 

 

이 작업은 배열의 길이를 고정하고 초기 값을 지정하도록 목적을 갖습니다. 

 

null 값을 사용하는 이유는 자바스크립트에서 null은 '값이 없음'을 나타내며, 이후에 요소를 변경하는 데 도움을 줍니다.

 

map(() => []): fill(null)로 채워진 배열의 각 원소를 새로운 빈 배열([])로 매핑합니다. 

map() 함수는 인자로 주어진 함수를 사용하여 배열의 각 요소를 새 요소로 변환하고 새 배열을 반환합니다. 

 

여기서 화살표 함수 () => []는 간단한 함수로 아무 인수도 받지 않고 빈 배열 []을 반환하는 역할을 수행합니다. 

 

결과적으로 

이 코드는 (v + 1) 길이의 배열을 생성하고 각 요소마다 빈 배열을 할당하여 2차원 배열 형태의 인접 리스트를 생성합니다.

 

위의 코드는 자바스크립트에서 인접 리스트를 나타내기 위한 매우 일반적인 패턴입니다. 인접 리스트 구조는 그래프의 각 정점에 연결되어 있는 다른 정점들의 리스트를 저장하는 효율적인 방법입니다. 이 구조를 사용하여 간편하게 정점 간의 관계를 나타내고, 그래프 관련 알고리즘에 사용할 수 있습니다.

 

 

[백준 코딩테스트 문제]  2178번 미로 찾기 큐 (BFS) 문제

 

[백준 코딩테스트 문제]  2178번 미로찾기 큐 (BFS) 문제


너비 우선 탐색(Breadth-First Search, BFS) 알고리즘


시간제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1초 192 MB 168873 75195 48130 43.159%
문제
N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1


미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1 
4 6
101111
101010
101011
111011

 

예제 출력 1 
15

 

미로 찾기 

 

방향키 이해도

 

마이너스가 왼쪽, 위

플러스가 오른쪽, 아래

                             ↑

                            (-1, 0)

      ←  (0, -1)        방향         (0, 1)  →
         
                             (1, 0)

                                ↓

   

 

정답코드

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

const [N, M] = input.shift().split(" ").map(Number);
const maze = input.map((line) => line.split("").map(Number));

const moveX = [-1, 0, 0, 1];
const moveY = [0, -1, 1, 0];

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
  isEmpty() {
    return this._arr.length === 0;
  }
}

function bfs(x, y) {
  const queue = new Queue();
  queue.enqueue([x, y]);

  while (!queue.isEmpty()) {
    const [curX, curY] = queue.dequeue();

    for (let i = 0; i < 4; i++) {
      const nextX = curX + moveX[i];
      const nextY = curY + moveY[i];

      if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
      if (maze[nextX][nextY] === 1) {
        maze[nextX][nextY] = maze[curX][curY] + 1;
        queue.enqueue([nextX, nextY]);
      }
    }
  }

  return maze[N - 1][M - 1];
}

console.log(bfs(0, 0));

 

 

 

정답 코드의 이해 주석

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

const [N, M] = input.shift().split(" ").map(Number);
const maze = input.map((line) => line.split("").map(Number));

const moveX = [-1, 0, 0, 1];
const moveY = [0, -1, 1, 0];

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
  isEmpty() {
    return this._arr.length === 0;
  }
}

function bfs(x, y) {
  const queue = new Queue();
  queue.enqueue([x, y]);

  while (!queue.isEmpty()) {
    const [curX, curY] = queue.dequeue();

    for (let i = 0; i < 4; i++) {
      const nextX = curX + moveX[i];
      const nextY = curY + moveY[i];

      if (nextX < 0) {
	  // 다음 위치의 x 좌표가 0보다 작으면 범위를 벗어남
	  continue; // 이동할 수 없으므로 다음 반복으로 넘어감
	}
	if (nextY < 0) {
	  // 다음 위치의 y 좌표가 0보다 작으면 범위를 벗어남
	  continue; // 이동할 수 없으므로 다음 반복으로 넘어감
	}
	
	
	
	if (nextX >= N) {
	  // 다음 위치의 x 좌표가 N보다 크거나 같으면 범위를 벗어남
	  continue; // 이동할 수 없으므로 다음 반복으로 넘어감
	}
	if (nextY >= M) {
	  // 다음 위치의 y 좌표가 M보다 크거나 같으면 범위를 벗어남
	  continue; // 이동할 수 없으므로 다음 반복으로 넘어감
	}
	if (maze[nextX][nextY] === 1) {
        maze[nextX][nextY] = maze[curX][curY] + 1;
        queue.enqueue([nextX, nextY]);
      }
    }
  }

  return maze[N - 1][M - 1];
}

console.log(bfs(0, 0));

 

[백준 코딩테스트 문제] js 내장함수 공부

 

[백준 코딩테스트 문제] js 내장함수 공부

js 내장함수

전역 함수:
eval()
parseInt()
parseFloat()
isNaN()
isFinite()
encodeURIComponent()
decodeURIComponent()


Array 함수:
concat()
every()
filter()
forEach()
indexOf()
join()
lastIndexOf()
map()
pop()
push()
reduce()
reduceRight()
reverse()
shift()
slice()
some()
sort()
splice()
unshift()


String 함수:
charAt()
charCodeAt()
concat()
endsWith()
fromCharCode()
includes()
indexOf()
lastIndexOf()
localeCompare()
match()
repeat()
replace()
search()
slice()
split()
startsWith()
substr()
substring()
toLocaleLowerCase()
toLocaleUpperCase()
toLowerCase()
toString()
toUpperCase()
trim()
valueOf()

 


Number 함수:
isFinite()
isInteger()
isNaN()
isSafeInteger()
parseFloat()
parseInt()
toExponential()
toFixed()
toPrecision()
toString()
valueOf()


Date 함수:
getDate()
getDay()
getFullYear()
getHours()
getMilliseconds()
getMinutes()
getMonth()
getSeconds()
getTime()
getTimezoneOffset()
setDate()
setFullYear()
setHours()
setMilliseconds()
setMinutes()
setMonth()
setSeconds()
setTime()
toDateString()
toISOString()
toJSON()
toLocaleDateString()
toLocaleTimeString()
toString()
toTimeString()
toUTCString()

 

[백준 코딩테스트 문제]   4963번 섬의 개수 (BFS)

 

[백준 코딩테스트 문제]   4963번 섬의 개수 (BFS)

 

4963번

시간제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1초 128 MB 60670 30668 21936 49.287%
문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.



한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력
각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력 1 
1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

 

예제 출력 1 
0
1
1
3
1
9 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

while (input.length) {
  const [w, h] = input
    .shift()
    .split(" ")
    .map(Number);

  if (w === 0 && h === 0) break;

  const map = Array.from({ length: h }, () => input.shift().split(" ").map(Number));

  const dx = [-1, -1, 0, 1, 1, 1, 0, -1];
  const dy = [0, 1, 1, 1, 0, -1, -1, -1];

  class Queue {
    constructor() {
      this._arr = [];
    }
    enqueue(item) {
      this._arr.push(item);
    }
    dequeue() {
      return this._arr.shift();
    }
    isEmpty() {
      return this._arr.length === 0;
    }
  }

  function bfs(x, y) {
    const queue = new Queue();
    queue.enqueue([x, y]);
    map[x][y] = 0;

    while (!queue.isEmpty()) {
      const [curX, curY] = queue.dequeue();

      for (let d = 0; d < 8; d++) {
        const nextX = curX + dx[d];
        const nextY = curY + dy[d];

        if (nextX >= 0 && nextY >= 0 && nextX < h && nextY < w && map[nextX][nextY] === 1) {
          map[nextX][nextY] = 0;
          queue.enqueue([nextX, nextY]);
        }
      }
    }
  }

  let cnt = 0;

  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (map[i][j] === 1) {
        bfs(i, j);
        cnt++;
      }
    }
  }

  console.log(cnt);
}

 

[백준 코딩테스트 문제] 2580번 스도쿠 문제 (BFS)

 

[백준 코딩테스트 문제] 2580번 스도쿠 문제 (BFS)

 2667번

시간제한 메모리 제한 제출 정답 맞힌 사람 정답 비[율
1초 128 MB 158821 70005 44376 41.966%


문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.



입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그다음 N 줄에는 각각 N개의 자료(0 혹은 1)가 입력된다.

출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지 내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1 
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000


예제 출력 1 
3
7
8
9

 

const fs = require("fs");

function getInputData() {
  const inputData = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
  const areaSize = Number(inputData.shift());
  const area = inputData;
  return { areaSize, area };
}

function initializeVisitedArray(areaSize) {
  return Array.from({ length: areaSize }, () => Array(areaSize).fill(false));
}

function getDirections() {
  return [[1, 0], [-1, 0], [0, 1], [0, -1]];
}

function isInArea(x, y, areaSize) {
  return x >= 0 && x < areaSize && y >= 0 && y < areaSize;
}

function bfs(i, j, areaSize, visited, area) {
  const queue = [];
  visited[i][j] = true;
  let count = 1;
  queue.push({ x: i, y: j });

  const directions = getDirections();

  while (queue.length > 0) {
    const { x, y } = queue.shift();

    for (const direction of directions) {
      const newX = x + direction[0];
      const newY = y + direction[1];

      if (
        isInArea(newX, newY, areaSize) &&
        area[newX][newY] === "1" &&
        !visited[newX][newY]
      ) {
        visited[newX][newY] = true;
        queue.push({ x: newX, y: newY });
        count++;
      }
    }
  }

  return count;
}

function findComplexes(areaSize, area) {
  const visited = initializeVisitedArray(areaSize);
  const complexSizes = [];

  for (let i = 0; i < areaSize; i++) {
    for (let j = 0; j < areaSize; j++) {
      if (area[i][j] === "1" && !visited[i][j]) {
        const complexSize = bfs(i, j, areaSize, visited, area);
        complexSizes.push(complexSize);
      }
    }
  }

  return { totalCount: complexSizes.length, complexSizes: complexSizes.sort((a, b) => a - b) };
}

function printResults(totalCount, complexSizes) {
  console.log(totalCount);
  complexSizes.forEach((size) => console.log(size));
}

function main() {
  const { areaSize, area } = getInputData();
  const { totalCount, complexSizes } = findComplexes(areaSize, area);
  printResults(totalCount, complexSizes);
}

main();
반응형
저작자표시 비영리 변경금지

'컴퓨터공부 > ASAC 웹풀스택' 카테고리의 다른 글

ASAC 웹풀스택 웹 통신 이해 딥다이브  (0) 2023.07.31
ASAC 웹풀스택 브라우저 딥다이브  (0) 2023.07.31
[ASAC 웹풀스택 개발자과정] 02. 코딩테스트 백준 브론즈탈출을 목표로 간다  (0) 2023.07.27
[ASAC 웹풀스택 개발자과정] 01. 코딩테스트 백준 브론즈탈출을 목표로 간다  (0) 2023.07.27

관련글

댓글

티스토리툴바