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

 

10026번: 적록색약

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

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 적록색약을 가진 분들과 적록색약이 아닌 분들이 보는 것이 다르다는 것을 이용한 문제입니다.

그것을 제외하고는 일반적인 bfs 문제와 같습니다. 예시를 들면 다음과 같습니다.

위의 그림이 있을 때 적록색약이 아닌 분들은 R, G, B로 3가지 구역, 적록색약인 분들은 RG, B로 2가지 구역으로 보는 것입니다. 따라서 이 점에 유의하며 bfs를 구현하면 됩니다.

문제 해결을 위한 팁

저의 경우는 그래프를 2개로 하여 기존에 입력받은 그래프를 복사하여 사용하였습니다. 이를 copy를 이용하였는데 copy의 경우 shallow copy, deep copy가 존재합니다. shallow copy의 경우 원본 혹은 복사본을 수정할 경우 기존의 그래프 역시 수정이 되므로 deep copy를 사용하여야 합니다. 따라서 import copy, 원본 = copy.deepcopy(복사본)를 사용합니다.

소스코드
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from collections import deque
import copy
 
def bfs(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if graph[nx][ny] == target:
        graph[nx][ny] = 'a'
        q.append((nx, ny))
 
def bfs2(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if target == 'R' or target == 'G':
        if graph[nx][ny] == 'R' or graph[nx][ny] == 'G':
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      else:
        if graph[nx][ny] == target:
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      
        
 
n = int(input())
graph = [['a'] * n for _ in range(n)]
for i in range(n):
  inputData = list(input()) 
  for j in range(n):
    graph[i][j] = inputData[j]
 
graph2 = copy.deepcopy(graph)
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
count = 0
for i in range(n):
  for j in range(n):
    if graph[i][j] != 'a':
      bfs(graph, i, j)
      count += 1
 
print(count, end=" ")
 
count = 0
for i in range(n):
  for j in range(n):
    if graph2[i][j] != 'a':
      bfs2(graph2, i, j)
      count += 1
 
print(count)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14

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

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 전형적인 bfs의 형태는 아니지만 자주 등장하는 형태입니다. 따라서 이러한 유형을 bfs로 푸는 것에 익숙해져야 합니다. 수빈이가 이동할 수 있는 곳인 (현재 위치 -1, 현재 위치 +1, 현재 위치 * 2)를 bfs의 형태로 탐색을 하여 해결합니다. 다만 주의해야 할 점은 리스트의 범위입니다. 이러한 문제의 경우 인덱스 에러가 쉽게 발생할 수 있으므로 범위에 신경을 써서 문제를 해결해주셔야 합니다. 소스코드는 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import deque
 
def bfs(n, k):
  q = deque()
  q.append(n)
  visited[n] = 1
  while q:
    v = q.popleft()
    for i in [v-1, v+1, 2*v]:
      if 0 <= i < 100001 and visited[i] == 0:
        visited[i] = visited[v] + 1
        q.append(i)
      if i == k:
        return visited[i] - 1
 
n, k = map(int, input().split())
visited = [0] * 100001
 
print(bfs(n, k))
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12
백준 알고리즘 11723번: 집합(Python)  (0) 2022.01.10

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

 

7576번: 토마토

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

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 단순한 BFS에서 아주 조금 응용을 하면 쉽게 해결할 수 있는 문제였습니다. 그래프를 입력받을 때 토마토가 들어있는 좌표를 따로 tomato라는 deque를 만들어 저장한다면 쉽게 해결할 수 있었습니다. 그 후로는 일반적인 bfs문제를 풀 때처럼 bfs를 적용합니다. 다만 전체 상자 안에 토마토가 익으려면 며칠이 걸리는지를 물어보는 문제였기 때문에 while 문 안에 for _ in range(len(tomato))를 두어서 이 해당하는 for문을 벗어날 때만 하나씩 count를 증가시켜주면 됩니다. for문을 추가해주는 이유는 한 번에 즉 하루에 bfs로 탐색할 수 있는 양이 tomato라는 deque에 추가되기 때문에 이 deque의 전체가 비면 하루가 지난 것 이기 때문입니다. 추가적으로 bfs로 탐색 후 전체 그래프에서 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from collections import deque
 
def bfs(grpah, tomato):
  count = 0
  while tomato:
    for _ in range(len(tomato)):
      x, y = tomato.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
          continue
        if graph[nx][ny] == 0:
          graph[nx][ny] = 1
          tomato.append((nx, ny))
    count += 1
  return count
 
m, n = map(int, input().split())
graph = []
tomato = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(m):
    if graph[i][j] == 1:
      tomato.append((i, j))
 
day = bfs(graph, tomato)
 
numOfZero = 0
for i in range(n):
  for j in range(m):
    if graph[i][j] == 0:
      numOfZero += 1
 
if numOfZero == 0:
  print(day-1)
else:
  print(-1)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12
백준 알고리즘 11723번: 집합(Python)  (0) 2022.01.10
백준 알고리즘 14499번: 주사위 굴리기(Python)  (0) 2022.01.10

www.acmicpc.net/problem/2468

 

2468번: 안전 영역

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

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 조금 특이하지만 BFS를 이용하면 해결할 수 있는 문제였습니다. 먼저 그래프를 입력받을 때 그래프의 원소들 중 최댓값 max를 확인합니다. 그 후 3중 for문을 이용하여 해결하는데 가장 바깥 for문은 0부터 max-1까지(max의 경우 모든 지역이 물에 잠기므로 안전영역이 무조건 0이다 따라서 확인할 필요가 없음)이고 그 안쪽 for문은 행과 열을 조회하는 이중 for문이다. 이렇게 조회를 하는데 방문하지 않은 지역이고 비가 온곳 보다 높은 지역이라면 bfs함수를 호출한다. 마찬가지로 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
31
32
33
34
35
36
37
38
39
40
41
42
from collections import deque
 
n = int(input())
graph = []
max = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] > max:
            max = graph[i][j] # 그래프의 원소들 중 최댓값을 찾음
 
def bfs(xPos, yPos, value, visited):
    q = deque()
    q.append((xPos, yPos))
    visited[xPos][yPos] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] > value and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
   
maximum = 0
for a in range(max): # 비가 안오는 경우인 0부터 max-1까지 조회(max는 모든 지역이 물에 잠기므로 안전영역이 0임 고려할 필요가 없음)
    visited = [[0] * n for _ in range(n)] # 매 높이마다 조회를 해야하므로 visited를 매번 정의
    ans = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > a and visited[i][j] == 0: # 비가 온것보다 높은 곳이고 방문하지 않은 경우 bfs호출
                bfs(i, j, a, visited)
                ans += 1
    if maximum < ans:
        maximum = ans
print(maximum)
                
               
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 9012: 괄호 (Python)  (0) 2021.02.06
백준 알고리즘 9095: 1, 2, 3 더하기(Python)  (0) 2021.02.06
백준 알고리즘 11724: 연결 요소의 개수(Python)  (0) 2021.02.05
백준 알고리즘 1012: 유기농 배추(Python)  (0) 2021.02.05
백준 알고리즘 14503: 로봇 청소기(Python)  (0) 2021.02.03

+ Recent posts

티스토리툴바