[백준] 7562번 나이트의 이동

[백준] 7562번 나이트의 이동

출처: [백준] 7562번 나이트의 이동


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 25244 12068 9035 46.974%

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

img


입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.


출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
10
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

1
2
3
5
28
0

출처


링크


알고리즘 분류


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import sys
from collections import deque

input = sys.stdin.readline

T = int(input())

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)]


def BFS(graph, start):
queue = deque([start])

while queue:
# 큐에서 하나의 원소를 뽑아 출력하기
r, c = queue.popleft()
if r == target_row and c == target_column:
return graph[r][c]
for step in steps:
# 이동하고자 하는 위치 확인
next_row = r + step[0]
next_col = c + step[1]
# 해당 위치로 이동이 가능하다면 카운트 증가
if 0 <= next_row < I and 0 <= next_col < I and graph[next_row][next_col] == 0:
graph[next_row][next_col] = graph[r][c] + 1
queue.append((next_row, next_col))


for _ in range(T):
I = int(input())
chess_board = [[0] * (I + 1) for _ in range(I + 1)]

row, column = map(int, input().split())
target_row, target_column = map(int, input().split())
result = BFS(chess_board, (row, column))
print(result)

[백준] 11725번 트리의 부모 찾기

[백준] 11725번 트리의 부모 찾기

출처: [백준] 11725번 트리의 부모 찾기


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 21429 9096 6766 43.043%

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.


입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.


출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.


예제 입력 1

1
2
3
4
5
6
7
7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

1
2
3
4
5
6
4
6
1
3
1
4

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12
12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2

1
2
3
4
5
6
7
8
9
10
11
1
1
2
3
3
4
4
5
5
6
6

출처

  • 문제를 만든 사람: baekjoon
  • 잘못된 조건을 찾은 사람: jh05013

알고리즘 분류


풀이


소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())

trees = {}
for i in range(N):
trees[i + 1] = set()

for i in range(N - 1):
a, b = map(int, input().split())
trees[a].add(b)
trees[b].add(a)

parents = [False] * (N + 1)


def dfs(graph, v, visited):
for i in graph[v]:
if not visited[i]:
visited[i] = v
dfs(graph, i, visited)


dfs(trees, 1, parents)
for i in range(2, N + 1):
print(parents[i])

[백준] 1987번 알파벳

[백준] 1987번 알파벳

출처: [백준] 1987번 알파벳


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 49798 15713 9586 29.155%

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.


입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.


출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.


예제 입력 1

1
2
3
2 4
CAAB
ADCB

예제 출력 1

1
3

기타 입력

1
2
3
4
3 4
ABBC
ECED
FGDH

기타 출력

1
8

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2002 > Regional Competition - Juniors 3번


링크


알고리즘 분류


풀이


소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys

input = sys.stdin.readline

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


def dfs(x, y, count):
global ans
ans = max(ans, count)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C and passed[board[nx][ny]] == 0:
passed[board[nx][ny]] = 1
dfs(nx, ny, count + 1)
passed[board[nx][ny]] = 0


R, C = map(int, input().split())
board = [list(map(lambda x: ord(x) - 65, input().rstrip())) for _ in range(R)]
passed = [0] * 26

ans = 1
passed[board[0][0]] = 1
dfs(0, 0, ans)

print(ans)

소스코드_BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys

input = sys.stdin.readline

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


def bfs():
global count
queue = set()
queue.add((0, 0, board[0][0]))

while queue:
x, y, ans = queue.pop()

for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in ans:
queue.add((nx, ny, ans + board[nx][ny]))
count = max(count, len(ans) + 1)


R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
count = 1
bfs()
print(count)

소스코드_실패(메모리 초과)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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


def dfs(x, y, cnt):
global count
count = max(cnt, count)

for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < R and 0 <= ny < C and board[nx][ny] not in passed:
passed.append(board[nx][ny])
dfs(nx, ny, cnt + 1)
passed.append(board[nx][ny])


R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
passed = []
count = 1
dfs(0, 0, count)
print(count)

[백준] 2644번 촌수계산

[백준] 2644번 촌수계산

출처: [백준] 2644번 촌수계산


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20625 9485 7194 45.397%

문제

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.


입력

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.


출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
10
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 출력 1

1
3

출처

Olympiad > 한국정보올림피아드 > KOI 1999 > 중등부 1번


알고리즘 분류


풀이


소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys

input = sys.stdin.readline

N = int(input())
comp1, comp2 = map(int, input().split())
M = int(input())
family = {}
for i in range(N):
family[i + 1] = set()
for i in range(M):
x, y = map(int, input().split())
family[x].add(y)
family[y].add(x)



def dfs(graph, target, count):
visited[target] = count
for i in graph[target]:
if not visited[i]:
dfs(graph, i, count + 1)


visited = [False] * (N + 1)
dfs(family, comp2, 1)
if not visited[comp1]:
print(-1)
else:
print(visited[comp1] - 1)

[백준] 10026번 적록색약

[백준] 10026번 적록색약

출처: [백준] 10026번 적록색약


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19449 11275 8904 58.025%

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

1
2
3
4
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.


입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.


출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.


예제 입력 1

1
2
3
4
5
6
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1

1
4 3

출처

Olympiad > USA Computing Olympiad > 2013-2014 Season > USACO March 2014 Contest > Bronze 3번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: corea

알고리즘 분류


풀이


소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(matrix, x, y, value):
matrix[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < N and 0 <= ny < N:
if matrix[nx][ny] == value:
dfs(matrix, nx, ny, value)


N = int(input())
grid = [list(input().rstrip()) for _ in range(N)] # people(R,G,B)
grid2 = [[0] * N for _ in range(N)] # people(R=G, B)

for i in range(N):
for j in range(N):
if grid[i][j] == 'R' or grid[i][j] == 'G':
grid2[i][j] = 1
else:
grid2[i][j] = 2

rgb_count = 0
b_count = 0
for i in range(N):
for j in range(N):
if grid[i][j] != 0:
dfs(grid, i, j, grid[i][j])
rgb_count += 1

if grid2[i][j] != 0:
dfs(grid2, i, j, grid2[i][j])
b_count += 1

print(rgb_count, b_count)

[백준] 2583번 영역 구하기

[백준] 2583번 영역 구하기

출처: [백준] 2583번 영역 구하기


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21003 11698 9290 56.702%

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

img

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.


입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.


출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.


예제 입력 1

1
2
3
4
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

예제 출력 1

1
2
3
1 7 13

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 고등부 2번


알고리즘 분류


풀이


소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y, count):
ground[x][y] = 1
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < M and 0 <= ny < N:
if ground[nx][ny] == 0:
count = dfs(nx, ny, count + 1)
return count


M, N, K = map(int, input().split())
ground = [[0] * N for _ in range(M)]

for _ in range(K):
x1, y1, x2, y2 = map(int, input().split())

for i in range(y1, y2):
for j in range(x1, x2):
ground[i][j] = 1

count = []
for i in range(M):
for j in range(N):
if ground[i][j] == 0:
count.append(dfs(i, j, 1))

print(len(count))
for x in sorted(count):
print(x, end=" ")
[백준] 2468번 안전 영역

[백준] 2468번 안전 영역

출처: [백준] 2468번 안전 영역


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 40557 15312 10254 34.415%

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

img

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

img

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

img

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.


입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.


출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.


예제 입력 1

1
2
3
4
5
6
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

예제 출력 1

1
5

노트

아무 지역도 물에 잠기지 않을 수도 있다.


출처

Olympiad > 한국정보올림피아드 > KOI 2010 > 초등부 2번

  • 문제의 오타를 찾은 사람: apjw6112
  • 어색한 표현을 찾은 사람: jh05013
  • 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류


풀이


소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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


def dfs(x, y, h):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < N and 0 <= ny < N and ground[nx][ny] > h and not visited[nx][ny]:
visited[nx][ny] = True
dfs(nx, ny, h)


N = int(input())
ground = [list(map(int, input().split())) for _ in range(N)]

result = 0
for k in range(max(max(ground))):
count = 0
visited = [[False] * N for _ in range(N)]
for i in range(N):
for j in range(N):
if ground[i][j] > k and not visited[i][j]:
count += 1
visited[i][j] = True
dfs(i, j, k)
result = max(result, count)
print(result)
[백준] 4963번 섬의 개수

[백준] 4963번 섬의 개수

출처: [백준] 4963번 섬의개수


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 30659 15375 11056 49.234%

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

img

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

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


입력

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

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

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


출력

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


예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

1
2
3
4
5
6
0
1
1
3
1
9

출처

ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2009 Japan Domestic Contest B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: j4bez

링크


알고리즘 분류


풀이


소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

# 방향정의 (상,하,좌,우, 1,5,7,9)
dx = [-1, 1, 0, 0, -1, 1, 1, -1]
dy = [0, 0, -1, 1, 1, 1, -1, -1]


def dfs(x, y):
ground[x][y] = -1

for i in range(8):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < H and 0 <= ny < W and ground[nx][ny] == 1:
dfs(nx, ny)


while True:
W, H = map(int, input().split())
if W == 0 and H == 0:
break

ground = [list(map(int, input().split())) for _ in range(H)]

count = 0
for i in range(H):
for j in range(W):
if ground[i][j] == 1:
dfs(i, j)
count += 1
print(count)

[백준] 11724번 연결 요소의 개수

[백준] 11724번 연결 요소의 개수

출처: [백준] 11724번 연결 요소의 개수


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 42149 20184 13181 44.965%

문제

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


입력

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


출력

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


예제 입력 1

1
2
3
4
5
6
6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

1
2

예제 입력 2

1
2
3
4
5
6
7
8
9
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1
1

힌트


출처


알고리즘 분류


풀이


소스코드_DFS(List1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(graph, v, visited):
visited[v] = True
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)


N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
component = 0

for _ in range(M):
src, dest = map(int, input().split())
graph[src].append(dest)
graph[dest].append(src)

for i in range(1, N + 1):
if not visited[i]:
dfs(graph, i, visited)
component += 1

print(component)

소스코드_DFS(List2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(graph, v, visited):
visited[v] = True
for i in range(1, N + 1):
if not visited[i] and graph[v][i] == 1:
dfs(graph, i, visited)


N, M = map(int, input().split())
graph = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
x, y = map(int, input().split())
graph[x][y] = 1
graph[y][x] = 1

visited = [False] * (N + 1)
component = 0

for i in range(1, N + 1):
if not visited[i]:
dfs(graph, i, visited)
component += 1
print(component)

소스코드_DFS(Dict)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(graph, v, visited):
visited[v] = True
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)


N, M = map(int, input().split())
graph = {}
for i in range(N + 1):
graph[i] = set()

for _ in range(M):
u, v = map(int, input().split())
graph[u].add(v)
graph[v].add(u)

visited = [False] * (N + 1)
component = 0

for i in range(1, N + 1):
if not visited[i]:
dfs(graph, i, visited)
component += 1

print(component)

[백준] 2667번 단지번호붙이기

[백준] 2667번 단지번호붙이기

출처: [백준] 2667번 단지번호붙이기


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 80852 33112 20949 39.110%

문제

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

img


입력

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


출력

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


예제 입력 1

1
2
3
4
5
6
7
8
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1

1
2
3
4
3
7
8
9

힌트


출처


알고리즘 분류


풀이


소스코드_DFS(List)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

# 방향 정의(상,하,좌,우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y, house):
ground[x][y] = 0 # 해당 지점은 확인

for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < N and 0 <= ny < N:
if ground[nx][ny] == 1:
house = dfs(nx, ny, house + 1)
return house


N = int(input())
ground = [list(map(int, input().rstrip())) for _ in range(N)]
houses = [] # 각 단지내 집의 수

for i in range(N):
for j in range(N):
if ground[i][j] == 1:
houses.append(dfs(i, j, 1))

print(len(houses))
for house in sorted(houses):
print(house)