문제https://www.acmicpc.net/problem/9205 풀이최대 20병이 들어가는 맥주 한 박스를 들고 출발하여 50m마다 맥주를 한 병씩 마시면서 가야 할 때, 상근이네 집에서 페스티벌에 갈 수 있으면 "happy"를, 그렇지 않으면 "sad"를 출력한다.편의점 개수 + 3(편의점 개수, 상근이 집 좌표, 페스티벌 좌표 입력) 씩 인덱스를 증가시키면서 테스트 케이스를 입력받는다.한 박스에 20병을 넣을 수 있고, 50m마다 맥주 한 병을 마셔야 하기 때문에 최대 이동할 수 있는 거리는 20x50=1000m이다. 따라서 서 맥주를 채울 수 있는 편의점까지 이동할 때, 또는 도착지인 페스티벌 좌표까지 이동할 때 거리가 1000m가 넘어가면 갈 수 없다.편의점을 무조건 순서대로 방문하는 것이 ..
문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 치즈의 바깥 가장자리 부분만 돌면서 값을 변경해야 하는데, 이를 위해 치즈(1)이 아닌 바깥쪽(0)을 BFS 탐색한다. 0이면 BFS로 계속 탐색하고, 1이면 nodes에 넣고 탐색이 끝난 후에 0으로 변경해 준다. - [0, 0]에서 시작해 bfs - [nx, ny]가 0이면 bfs 대상 -> queue.push() - [nx, ny]가 1이면 녹일 대상 -> 0으로 변경 - 이 과정을 치즈가 없을 때까..
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 0은 빈 칸, 1은 벽, 2는 바이러스가 있고, 바이러스는 4방향으로 퍼져나갈 수 있다. 이때 벽을 3개 세운 뒤 바이러스가 퍼질 수 없는 영역인 안전 영역의 최대 크기를 찾는 문제이다. 1. 0인 구간 가운데 3개 고르기 (3중 for문 또는 DFS) 2. 2인 경우 큐에 넣어서 BFS 돌리면서 2로 바꾸고 3. 전체 탐색하면서 0인 곳 개수 세서 최댓값 찾기 이때 주의해야할 점은 3개를 선정하고..
문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 문제를 읽고 숫자고르기와 같이 각 요소에서 DFS 탐색을 해야 한다는 걸 알 수 있었다. 주어진 입력으로 양방향 그래프를 만들고, 각 1~N에서 각각 방문 표시 배열(ch)을 이용한 DFS를 한다. 이때 flag 변수를 사용하여 연결된 노드가 5개가 나오는 경우 return 해서 DFS를 종료한다. 또한 flag가 1인 경우, 즉 A, B, C, D, E가 존재하는 경우, for문을 종료한다. flag가 1이면 1을 아니면 0을 출력한다. 처음에는 DFS에서 연결된 개수를 반환해주고, 다 돌..
문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 이전에 풀었던 방식과 유사하지만 nodes라는 하나의 배열을 이용해 인구 이동을 조금 더 간단하게 구현하였다. 2중 for문으로 각각의 땅에서 BFS를 돌고 이동 가능한 경우 nodes 배열에 담아둔다. BFS가 끝나면 nodes 배열에 담긴 좌표들은 인구 이동을 해준다. nodes 배열에 자기 자신만 담긴 경우(nodes.length === 1) 이동하지 못했다는 의미이..
문제 https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 class Queue { constructor() { this.data = []; this.head = 0; this.tail = 0; } push(item) { this.data[this.tail++] = item; } pop() { this.head++; } front() { return this.data[this.head]; } rear() { return this..
문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 class Queue { constructor() { this.data = []; this.head = 0; this.tail = 0; } push(item) { this.data[this.tail++] = item; } pop() { this.head++; } front() { return this.data[this.head]; } rear() { return this...
