https://www.acmicpc.net/problem/7576

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1 복사

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1 복사

8

풀이

  • 하루가 지나면 익은 토마토의 인접한 토마토(상하좌우)가 익는다. -> 익은 토마토(1)를 큐에 넣고 주변에 익지 않은 토마토가 있으면 해당 위치값을 1(하루) 증가시킨다: 
  • 큐에 남은 게 없을 때까지 BFS를 실행하게 되면 아래 그림과 같은 모습이 된다.

  • 1인 값부터 시작했기 때문에 배열에서 가장 큰 수를 찾아 -1을 빼주면 토마토가 모두 익은 일수를 구할 수 있다.

코드

from collections import deque;

# 상하좌우 방향 벡터
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

check = 0   # 익지 않은 토마토(0)가 있다면 1을 넘겨줌
max = 0     # 최대 일수

def Bfs():
    # 값이 1인 곳의 상하좌우 탐색
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            # 해당 위치의 상하좌우의 값이 0(익지 않은 토마토)일 때 해당 값을 증가시켜서 최대 일수를 구함
            if board[nx][ny] == 0:
                q.append((nx, ny))
                board[nx][ny] = board[x][y] + 1

if __name__ == "__main__":
    # M: 가로, N: 세로
    M, N = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    q = deque()

    # 맵에서 1인 곳을 찾아 큐에 담고 BFS 실행
    for i in range(N):
        for j in range(M):
            if board[i][j] == 1:
                q.append((i, j))

    Bfs()

    # BFS가 끝난 후 2차원 배열에 0이 존재할 경우 
    for i in range(N):
        for j in range(M):
            # 익지 않은 토마토가 있으면 check 변수에 1 담고 이 값이 1일 때 -1 출력
            if board[i][j] == 0:
                check = 1
            
            # 가장 큰 값 max 변수에 담기
            if max < board[i][j]:
                max = board[i][j]

    # 출력하는 부분
    if check == 1:
        print(-1)
    else:
        print(max-1)

https://www.acmicpc.net/problem/10026

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

입력

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

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

출력

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

예제 입력 1 복사

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 복사

4 3

풀이

  • BFS 이용(DFS도 사용 가능)
  • 색약이 있는 사람들은 R, G를 모두 똑같은 색으로 인식한다. -> 'G'을 'R'로 변경('R' -> 'G'도 가능)
  • BFS 함수에서 상하좌우의 값을 확인하고 동일하면 큐에 집어 넣는다. 그래프의 모든 값을 확인하고 영역의 수를 구해야하는 문제이기 때문에 상하좌우의 값이 현재 큐에서 꺼낸 좌표에 들어있는 값과 같다면 큐에 넣은 후 다시 주변을 탐색한다.

!! 처음에는 BFS 함수의 매개변수로 색깔값을 받아왔는데, 이는 모든 값을 확인해줘야 하기 때문에 코드가 지저분하고 반복적인 부분이 많았다. 코드를 계속 치면서도 내가 조금 이상하고 복잡하게 풀고 있다는 느낌을 받았었는데 역시나 잘못된 방법이었다.

수정 전

def Bfs(x, y, color):
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if board[nx][ny] == color and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True

수정 후

def Bfs(x, y):
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if board[nx][ny] == board[x][y] and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True
  • 위 코드를 이용하면 메인 코드에서 방문 여부만 판단하여 그래프를 탐색할 수 있다.
  • 색약의 유무에 따라 영역의 수를 출력 -> BFS 2번 사용해야 하며 이때 방문 그래프와 영역의 수를 초기화한 뒤 BFS를 실행해야 한다.

코드

from collections import deque;

# 상하좌우 방향벡터
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 영역의 수
cnt = 0

def Bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            # 현재 값과 상하좌우 값 비교하여 같으면 큐에 집어 넣고 방문 처리를 해주는 부분
            if board[nx][ny] == board[x][y] and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True

if __name__ == "__main__":
    N = int(input())
    board = [list(input().strip()) for _ in range(N)]
    visited = [[False] * N for _ in range(N)]

    # 적록색약이 아닐 때
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                Bfs(i, j)
                cnt += 1
    
    # 줄바꿈X 공백 구분 위해 end=' ' 사용
    print(cnt, end=' ')

    # 적록색약일 때: G를 R로 변경해준 뒤 탐색
    for i in range(N):
        for j in range(N):
            if board[i][j] == 'G':
                board[i][j] = 'R'

    # 방문 배열, 영역의 수 초기화
    visited = [[False] * N for _ in range(N)]
    cnt = 0

    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                Bfs(i, j)
                cnt += 1

    print(cnt)

 

https://www.acmicpc.net/problem/1926

 

1926번: 그림

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로

www.acmicpc.net

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제 입력 1 복사

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1 복사

4
9

풀이

  • DFS 이용한 배열 탐색
  • 대각선으로 이어진 그림은 떨어진 그림 -> 상하좌우 방향벡터 이용하여 주변값 확인
  • 배열에 존재하는 그림 중 가장 넓은 그림을 출력하기 위해 배열에 넓이를 저장, max() 사용하여 출력

!! 런타임 에러(ValueError) 발생

result = []

print(max(result))

그림의 넓이를 담기 위해 result 배열을 생성 -> 해당 배열의 길이 0

max() 사용 시 배열이 비어있기 때문에 런타임 에러 발생

 

해결 방법

# 1. 배열이 비어있지 않도록 0 집어넣기
result = [0]

# 2. 출력할 때 예외 조건 부여하기
if len(result) == 0:
    print(0)
    print(0)
else:
    print(cnt)
    print(max(result))

 

코드

from collections import deque

# 상하좌우 방향벡터
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 넓이 저장 배열
result = []

# 그림의 개수
cnt = 0

def Dfs(x, y):
    area = 1                # 그림의 넓이
    q = deque()
    q.append((x, y))        # 좌표 데크에 넣어 저장
    visited[x][y] = True    # 방문 처리


    while q:
        x, y = q.pop()
        # 상하좌우 탐색해서 그림이 존재하면 데크에 위치값 저장 후 그림 넓이 1 증가
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            if board[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True
                area += 1
    return area


if __name__ == "__main__":
    # r: 열, c: 행
    r, c = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(r)]     # 한줄씩 값 채워넣기
    visited = [[False] * c for _ in range(r)]                       # 방문 배열

    for i in range(r):
        for j in range(c):
            if board[i][j] == 1 and not visited[i][j]:
                result.append(Dfs(i, j))                # 그림 넓이 저장
                cnt += 1                                # 그림 개수 증가
                visited[i][j] = True                    # 방문 처리
    
    # 그림이 없을 때는 그림의 넓이를 0으로 처리
    if len(result) == 0:
        print(0)
        print(0)
    else:
        print(cnt)
        print(max(result))

https://www.acmicpc.net/problem/1743

 

1743번: 음식물 피하기

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다

www.acmicpc.net

 

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

 

예제 입력 1 복사

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

예제 출력 1 복사

4

힌트

# . . .
. # # .
# # . .

위와 같이 음식물이 떨어져있고 제일큰 음식물의 크기는 4가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)


풀이

  •  BFS 사용하여 음식물의 개수 배열에 저장
  • 대각선으로는 음식물 덩어리가 될 수 없으므로 상하좌우 방향벡터 정의하여 탐색
  • 음식물이 존재할 때, 영역에 존재하는 음식물 개수를 증가하여 반환
  • 영역에 존재하는 총 음식물 개수(크기)를 배열에 담고 max 함수 사용하여 가장 큰 음식물 크기 출력

코드

from collections import deque;

#  상하좌우 방향벡터
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 음식물 담을 리스트
result = []

def Bfs(x, y):
    cnt = 1
    q = deque()
    q.append((x, y))
    visited[x][y] = True

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 탐색 범위 제한
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            # 음식물 쓰레기가 있고 방문하지 않았다면 개수 증가
            if board[nx][ny] == '#' and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True
                cnt += 1
    return cnt

if __name__ == "__main__":
    # N: 세로 M: 가로 K: 음식물 개수
    N, M, K = map(int, input().split())
    board = [['.'] * M for _ in range(N)]
    visited = [[False] * M for _ in range(N)]

    # 음식물 위치 받아오기
    # r, c는 좌표이므로 배열의 인덱스를 받아오기 위해 -1 해준다
    for _ in range(K):
        r, c = map(int, input().split())
        board[r-1][c-1] = '#'

    for i in range(N):
        for j in range(M):
            # 음식물 있으면 배열에 음식물 개수 저장
            if board[i][j] == '#' and not visited[i][j]:
                result.append(Bfs(i, j))

    # 배열에서 가장 큰 음식물 출력
    print(max(result))

https://www.acmicpc.net/problem/2468

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

 

문제

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

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


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


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

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

 

 

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

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

입력

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

출력

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

예제 입력 1 복사

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 복사

5

예제 입력 2 복사

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

예제 출력 2 복사

6

 

노트

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


풀이

  • (N,N) 크기의 2차원 배열 생성 후 높이 입력
  • BFS를 사용하여 값 탐색. 좌표값 x, y와 해당 위치값(높이)을 매개변수로 전달 -> Bfs(x, y, N)
  • 값이 높이(N)보다 높을 경우 BFS 실행하고 영역 개수 증가
  • 배열에 입력된 숫자들의 최소, 최대값만큼 반복문을 돌리면서 모든 높이에 대한 영역의 수 저장
  • min(map(min, board))/max(map(max, board)): map(func, iterable)은 해당 요소(iterable)를 특정 함수(func)로 변환해주는 함수이다. map 함수의 반환값은 map객체이기 때문에, list 또는 tuple로 변환하여 값을 얻어와야 한다. 아래 코드는 반환된 map 객체에서의 최소(min()), 최대(max())값을 추출한다.
# 예제 1 사용하여 board(2차원 배열)에 값 넣었을 경우
minHeight = min(map(min, board))	# 2
maxHeight = max(map(max, board))	# 9
  • range(x, y): x부터 y-1 범위
  • Bfs가 실행되면 방문 처리를 하기 때문에, 탐색 후 방문 배열 초기화 + 영역의 수 초기화
# 2부터 9까지 반복하고 싶을 경우
minHeight = 2
maxHeight = 9

for h in range(minHeight, maxHeight)	# h = [2, 3, 4, 5, 6, 7, 8] -> X
for h in range(minHeight, maxHeight + 1)	# h = [2, 3, 4, 5, 6, 7, 8, 9] -> O
  • 각 높이에 대한 영역의 수를 배열에 담고 max() 사용하여 최대값 출력

전체 코드

from collections import deque;

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

# 물에 잠기지 않은 영역의 수
cnt = 0

# 반복문을 돌면서 최대 영역을 저장하는 배열 -> max()사용하여 최대 영역 수 출력
arrArea = []

# Bfs 함수가 실행되면서 좌표를 데크에 저장
# 해당 좌표 방문 처리(True)
def Bfs(x, y, h):
    q = deque()
    q.append((x, y))
    visited[x][y] = True

    # 가장 앞부분부터 꺼내어 상하좌우 탐색
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 값이 맵 밖으로 벗어나면 실행 X
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            # 주변에 위치한 값이 매개변수로 받아온 높이보다 크거나 같고,
            # 방문하지 않았다면 큐에 저장하고 방문 처리 작업 진행
            if board[nx][ny] >= h and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True

if __name__ == "__main__":
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    visited = [[False] * N for _ in range(N)]

    # 입력한 2차원 배열의 최소, 최대값
    minHeight = min(map(min, board))
    maxHeight = max(map(max, board))

    # 높이의 값이 최소부터 최대일 때까지 반복문 실행 
    for h in range(minHeight, maxHeight + 1):
        # 방문 배열, 영역의 수 초기화 -> 방문 처리가 되어있으면 각 높이에 따른 Bfs 실행 불가
        visited = [[False] * N for _ in range(N)]
        cnt = 0

        # 배열의 크기만큼 반복문 돌면서 물에 잠기지 않고, 방문하지 않았다면 Bfs 실행하고 영역의 수 증가
        for i in range(N):
            for j in range(N):
                if board[i][j] >= h and not visited[i][j]:
                    Bfs(i, j, h)
                    visited[i][j] = True
                    cnt += 1
        arrArea.append(cnt)

    # 배열에 담긴 영역의 수 중 최대값 출력
    print(max(arrArea))

 

https://www.acmicpc.net/problem/2583

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

문제

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

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

<그림 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

 

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

예제 출력 1

3
1 7 13

풀이

  • 직사각형을 제외한 구역의 넓이 구하기 -> 배열을 1로 채우고 직사각형 좌표에 0 등록
  • DFS 사용하여 값 탐색(BFS 사용 가능)
  • DFS 실행 후 넓이 리스트에 저장 후 sort() 사용하여 오름차순 정렬

코드

from collections import deque;

#  상하좌우 방향벡터
dx = [0,0,1,-1]
dy = [1,-1,0,0]

result = []     # 영역의 개수를 담는 리스트
cnt = 0         # 분리 영역 개수

# dfs를 실행될 때마다 분리된 영역 개수(cnt) 증가
# 해당 x, y 값 데크에 저장하고 방문 처리(False -> True)
def Dfs(x, y):
    cnt = 1
    q = deque()
    q.append((x, y))
    visited[x][y] = True

    # 큐가 비어있지 않다면, 해당 좌표의 상하좌우를 탐색
    while q:
        x, y = q.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 배열 인덱스를 넘지 않도록 범위 설정
            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue
            # 탐색한 4방향의 값이 1이고 방문 리스트가 False일 경우 데크에 좌표값 저장 후 방문 처리, 영역 개수 증가
            if board[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True
                cnt += 1

    return result.append(cnt)   # 오름차순 정렬 위해 영역 개수 리스트에 담고 반환

if __name__ == "__main__":
    # N: 가로 M: 세로 K: 분리 영역 개수(0으로 채울 부분)
    # 입력은 세로, 가로(M, N)를 받음

    M, N ,K = map(int, input().split())
    board = [[1] * N for _ in range(M)]
    visited = [[False] * N for _ in range(M)]

    # 분리할 영역 0으로 채우기
    for _ in range(K):
        x1, y1, x2, y2 = map(int, input().split())
        for i in range(y1, y2):
            for j in range(x1, x2):
                board[i][j] = 0

    # 해당 좌표가 1이고 방문하지 않았으면 DFS 실행 후 영역 수 증가시키기
    for i in range(M):
        for j in range(N):
            if board[i][j] == 1 and not visited[i][j]:
                Dfs(i ,j)
                cnt += 1


# 오름차순 정렬
result.sort()

print(cnt)      # 3

for i in result:
    print(i, end=' ')   # 1 7 13

 

https://www.acmicpc.net/problem/4963

 

4963번: 섬의 개수

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

www.acmicpc.net

문제

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 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

 


풀이

  • 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있기 때문에 1개의 섬으로 취급
  • 가로, 세로, 대각선 총 8개의 방향 벡터를 선언하여 DFS로 8방향 탐색하고, 섬의 개수 1 증가
  • 입력의 마지막 줄에는 0이 2개 주어진다 -> 너비(w)와 높이(h)에 0을 입력하면 실행 종료: while문 사용하여 종료 조건 지정

코드

from collections import deque

# 상하좌우 대각선 방향
dx = [0,0,1,-1,1,1,-1,-1]
dy = [1,-1,0,0,-1,1,1,-1]

def dfs(x, y):
    # 위치 저장 후 데크에 넣고 방문처리
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    
    # 큐가 비어있지 않다면, 맨 뒤에 있는 값의 상하좌우, 대각선 탐색
    # 주변 좌표에 섬이 존재할 경우 큐에 넣고 방문 처리
    while q:
        x, y = q.pop()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if board[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx,ny))
                visited[nx][ny] = True

if __name__ == "__main__":
    while True:
        cnt = 0  # 섬의 개수
        w, h = map(int, input().split())    # 너비, 높이 입력
        board = [list(map(int, input().split())) for _ in range(h)]     # 지도 입력 받기
        visited = [[False] * w for _ in range(h)]   # 방문 체크 리스트
        
        # 입력값 '0 0'일 때 반복문 탈출
        if w == 0 and h == 0:
            break
        
        # 지도 탐색하며 섬이 있고, 방문하지 않았다면 dfs 실행 후 개수 증가
        for i in range(h):
            for j in range(w):
                if board[i][j] == 1 and not visited[i][j]:
                    dfs(i, j)
                    cnt += 1
        print(cnt)

 

 

https://www.acmicpc.net/problem/1303

 

1303번: 전쟁 - 전투

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는

www.acmicpc.net

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.

출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

예제 입력 1 

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

예제 출력 1 

130 65

풀이

  • 같은 팀의 병사들은 모이면 모일수록 강해지며 제곱의 위력 가짐
  • 같은 팀 병사들이 대각선으로 인접할 경우 뭉쳐있다고 보지 않기 때문에, BFS를 사용하여 상하좌우 탐색 후 병사의 수 저장
  • 위력의 합 출력 위해 위력 더하는 변수 2개(blue, white) 선언
  • BFS가 끝날 때, 위력 반환하여 모두 더한 뒤 출력
  • strip(): 병사 입력 받을 때 문자열 공백 삭제 함수 사용

코드 

from collections import deque;

# 상하좌우
dx = [0,0,1,-1]
dy = [1,-1,0,0]

# 병사의 수
cnt = 0

# 병사의 옷 색 (W, B)
color = ''

# 아군, 적군의 위력으로 제곱해서 더할 변수
blue = 0
white = 0

def bfs(x, y, color):
    # 현재 들어온 병사를 큐에 넣기 때문에 병사의 수(cnt)를 1로 시작
    # 방문 처리 위해 현재 좌표값을 True로 변경
    # 큐에 넣은 좌표값을 꺼내어 상하좌우 탐색 -> 해당 값이 있고 방문하지 않았다면, 큐에 넣고 병사의 수 증가
    # 병사 n명 뭉쳐있을 경우 제곱근의 위력 -> cnt^2 반환 
    cnt = 1
    q = deque()
    q.append((x,y))
    visited[x][y] = True

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if board[nx][ny] == color and not visited[nx][ny]:
                q.append((nx, ny))
                cnt += 1
                visited[nx][ny] = True  
    return cnt ** 2

if __name__ == "__main__":
    n, m = map(int, input().split())                        # 가로 세로 입력
    board = [list(input().strip()) for _ in range(m)]       # 병사의 옷 색 공백 없이 입력 받아 2차원 리스트 생성 
    visited = [[False] * n for _ in range(m)]               # 방문 확인 리스트

    for i in range(m):
        for j in range(n):
            if board[i][j] == 'W' and not visited[i][j]:    # 값이 'W'이고 방문하지 않았을 때 BFS 실행
                color = board[i][j]
                white += bfs(i, j, color)                   # 하얀 옷을 입은 병사의 위력 저장

            elif board[i][j] == 'B' and not visited[i][j]:  # 값이 'B'이고 방문하지 않았을 때 BFS 실행
                color = board[i][j]
                blue += bfs(i, j, color)                    # 파란 옷을 입은 병사의 위력 저장


print(white, blue)

+ Recent posts