[BaekJoon] 3197 백조의 호수 (Platinum 5) - Python
문제
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
...XXXXXX..XX.XXX ....XXXX.......XX .....XX..........
....XXXXXXXXX.XXX .....XXXX..X..... ......X..........
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X.....
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX....
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX....
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............
..XXXXX...XXX.... ....XX.....X..... .................
....XXXXX.XXX.... .....XX....X..... .................
처음 첫째 날 둘째 날
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
입출력 예시
입력: 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력: 첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
입력예시1)
10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L출력예시1)
3
입력예시2)
4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...출력예시2)
2
입력예시3)
8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...출력예시3)
2
코드
bfs로 두 백조가 만날 수 있는지 찾는 코드는 할만 했는데 ,,,,,
bfs탐색을 위한 얼음 위치정보? 그걸 어케해야할지 몰라서 인터넷 여기저기 보고 했다....
생각보다 원리는 쉽드라
좀만 더 생각해볼걸
1. 백조 위치를 따로 리스트에 저장하고, L을 .으로 바꾼다. (탐색하기 쉽게 하려고 그랬다고 한다.)
2. 다음날에 녹을 위치에 있는 얼음의 위치를 리스트에 저장한다.
3. 이 리스트를 bfs함수에 매개변수로 넘겨준다.
- bfs함수에서는 얼음 위치의 상하좌우를 탐색한다.
- 매개변수로 넘겨준 얼음 위치 리스트에서 한 개씩 pop하여 사용한다.
- 얼음 위치를 물('.')로 바꾸고, 상하좌우에 얼음이 있을 경우, 얼음이 있는 칸의 위치를 buf리스트에 추가한다.
- 얼음 위치 상하좌우에 물이 있는 경우 union_list에 물의 위치를 추가한다.
- 상하좌우 탐색이 끝나면 union_list에 있는 물의 위치와 현재 얼음의 위치를 union한다.
- 얼음 위치 리스트가 비어있을 때 까지 반복.
- buf리스트를 return 한다
4. bfs함수에서 return한 buf를 melt에 저장하고, 이 melt를 다시 bfs함수의 매개변수로 전달한다.
5. 3, 4를 두 백조가 만날 수 있을 때 까지 반복하고, 반복한 횟수를 day변수에 저장한다
6. day변수 출력
import sys
from collections import deque
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
N, M = map(int, input().rstrip().split())
grid = [list(input()) for _ in range(N)]
root = [[(i, j) for j in range(M)] for i in range(N)]
visit = [[False for _ in range(M)] for _ in range(N)]
swan = []
def in_range(x, y):
return (0 <= x < N and 0 <= y < M)
def find(x, y):
if (x, y) == root[x][y]:
return (x, y)
root[x][y] = find(root[x][y][0], root[x][y][1])
return root[x][y]
def union(x1, y1, x2, y2):
x1, y1 = find(x1, y1)
x2, y2 = find(x2, y2)
root[x2][y2] = (x1, y1)
def bfs(melt):
buf = deque()
while melt:
x, y = melt.popleft()
grid[x][y] = "."
union_list = []
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if in_range(nx, ny) and not visit[nx][ny] and grid[nx][ny] == "X":
visit[nx][ny] = True
buf.append((nx, ny))
elif in_range(nx, ny) and grid[nx][ny] == ".":
union_list.append((nx, ny))
for a in union_list:
bx, by = a[0], a[1]
if find(bx, by) != find(x, y):
union(bx, by, x, y)
return buf
for i in range(N):
for j in range(M):
if grid[i][j] == "L":
swan.append((i, j))
grid[i][j] = "."
if len(swan) == 2:
break
melt = deque()
for i in range(N):
for j in range(M):
if not visit[i][j] and grid[i][j] == ".":
q = deque()
q.append((i, j))
visit[i][j] = 1
while q:
x, y = q.popleft()
root[x][y] = (i, j)
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if in_range(nx, ny) and not visit[nx][ny] and grid[nx][ny] == ".":
visit[nx][ny] = True
q.append((nx, ny))
elif in_range(nx, ny) and not visit[nx][ny] and grid[nx][ny] == "X":
visit[nx][ny] = True
melt.append((nx, ny))
day = 0
while find(swan[0][0], swan[0][1]) != find(swan[1][0], swan[1][1]):
melt = bfs(melt)
day += 1
print(day)실행 화면
채점 결과
푸는데 1주일 걸려써 ㅇ.ㅇ
공부 더 해야게다