[스터디] 문제 풀이 - 6주차

실 - 1389, 2468, 2178
골 - 5014, 3190, 14499
프 - 행렬 테두리 회전하기

---

1389번

문제

파이썬 풀이

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().strip().split())
graph = [[] * (n+1) for _ in range(n+1)]
count = [[0] * (n+1) for _ in range(n+1)]
kevin = []

for _ in range(m):
    a, b = map(int, input().strip().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(s):
    visitied = [False] * (n + 1)
    visitied[s] = True
    q = deque([s])
    while q:
        t = q.popleft()
        for i in graph[t]:
            if not visitied[i]:
                visitied[i] = True
                q.append(i)
                count[s][i] = count[s][t] + 1

for i in range(1, n+1):
    bfs(i)

for i in range(1, n+1):
    kevin.append(sum(count[i]))
    
print(kevin.index(min(kevin)) + 1)

C++ 풀이

2468번

문제

파이썬 풀이

from collections import deque
import sys
input = sys.stdin.readline

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

maxRain = max(map(max, ground))
answer= 0

def bfs(x, y, h):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque()
    q.append((x, y))
    visitied[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 ny < 0 or nx >= n or ny >= n:
                continue
            if ground[nx][ny] > h and visitied[nx][ny] is False:
                q.append((nx, ny))
                visitied[nx][ny] = True
    
for h in range(maxRain+1):
    visitied = [[False] * n for _ in range(n)]
    temp = 0
    for i in range(n):
        for j in range(n):
            if visitied[i][j] is False and ground[i][j] > h:
                bfs(i, j, h)
                temp += 1
    answer = max(answer, temp)
    
print(answer)

C++ 풀이

2178번

문제

bfs로 탐색하며 이전 경로 +1

파이썬 풀이

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().strip().split())
graph = [list(map(int, input().strip())) for _ in range(n)]

def solution():
    q = deque()
    q.append((0, 0))
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    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 >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                q.append((nx, ny))
                
    return graph[n-1][m-1]

print(solution())

C++ 풀이

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<vector<int>> graph;

int solution(){
    int x, y, nx, ny;
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    queue<vector<int>> q;
    vector<int> temp = {0, 0};
    q.push(temp);
    while(!q.empty()){
        x = q.front()[0];
        y = q.front()[1];
        q.pop();
        for(int i = 0; i < 4; ++i){
            nx = x + dx[i];
            ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m)  {continue;}
            if(graph[nx][ny] == 1){
                graph[nx][ny] = graph[x][y] + 1;
                temp = {nx, ny};
                q.push(temp);
            }
        }
    }
    return graph[n-1][m-1];
}

int main(){
    int t;
    scanf("%d %d", &n, &m);
    graph = vector<vector<int>>(n, vector<int>(m));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            scanf("%1d", &graph[i][j]);
        }
    }
    printf("%d", solution());
}

scanf("%1d", &graph[i][j]);
연속된 숫자를 하나씩 받을 수 있다.

---

5014번

문제

파이썬 풀이

from collections import deque
import sys
input = sys.stdin.readline
MAX = 1000001


f, s, g, u, d = map(int, input().strip().split())

visitied = [False] * MAX
count = [0] * MAX
dx = [u, -d]
q = deque([s])

def bfs():
    visitied[s] = True
    while q:
        n = q.popleft()
        for i in range(2):
            nn = n + dx[i]
            if 0 < nn and nn <= f and not visitied[nn]:
                visitied[nn] = True
                q.append(nn)
                count[nn] = count[n] + 1

bfs()

if visitied[g]:
    print(count[g])
else:
    print("use the stairs")

C++ 풀이

3190번

문제

파이썬 풀이

import sys

input = sys.stdin.readline

n = int(input())
k = int(input())
board = [[0] * n for _ in range(n)]
direct = []

for _ in range(k):
    a, b = map(int, input().strip().split())
    board[a-1][b-1] = 1
    
l = int(input())
for _ in range(l):
    x, c = input().strip().split()
    direct.append((int(x), c))

# 동 북 서 남 순서
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

def turn(direction, c):
    if c == 'D':
        direction = (direction - 1) % 4     # cw
    else:
        direction = (direction + 1) % 4     # ccw
    return direction

x, y = 0, 0
board[x][y] = 2
q = [(x, y)]

direction = 0
time = 0
idx = 0

while True:
    time += 1 
    nx = x + dx[direction]
    ny = y + dy[direction]
    if 0 <= nx and nx < n and 0 <= ny and ny < n and board[nx][ny] != 2:
        if board[nx][ny] == 0:  # 사과 없는 곳
            q.append((nx, ny)) # 머리 이동
            board[nx][ny] = 2
            px, py = q.pop(0) # 꼬리 이동
            board[px][py] = 0
          
        if board[nx][ny] == 1:  # 사과 있는 곳
            q.append((nx, ny)) # 머리 이동
            board[nx][ny] = 2
        x, y = nx, ny
  
    else:
        break
  
    if idx < l and time == direct[idx][0]:
        direction = turn(direction, direct[idx][1])
        idx += 1

print(time)

C++ 풀이

14499번

문제

파이썬 풀이

C++ 풀이

---

행렬 테두리 회전하기

문제

시계 방향으로 돌면서 이전 원소를 넣어줌

파이썬 풀이

from collections import deque

def rotate(query):
    r1, c1, r2, c2 = query
    temp = []
    temp.append(0)
    
    for j in range(c1-1, c2-1):         # 상단
        temp.append(board[r1-1][j])
        board[r1-1][j] = temp[-2]

    for i in range(r1-1, r2-1):         # 오른쪽
        temp.append(board[i][c2-1])
        board[i][c2-1] = temp[-2]
        
    for j in range(c2-1, c1-1, -1):     # 하단
        temp.append(board[r2-1][j])
        board[r2-1][j] = temp[-2]
    
    for i in range(r2-1, r1-1, -1):     # 왼쪽
        temp.append(board[i][c1-1])
        board[i][c1-1] = temp[-2]
    
    board[r1-1][c1-1] = temp[-1]    
    del temp[0]

    return min(temp)


def solution(rows, columns, queries):
    answer = []
    global board
    board = [[0] * columns for _ in range(rows)]
        
    for i in range(rows):
        for j in range(columns):
            board[i][j] = i * columns + j + 1

    for q in queries:
        answer.append(rotate(q))
    
    return answer

C++ 풀이

#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> board;

int rotate(vector<int> query){
    vector<int> temp;
    temp.push_back(0);
    int r1, c1, r2, c2;
    r1 = query[0];  c1 = query[1];
    r2 = query[2];  c2 = query[3];
    
    for(int j = c1-1; j < c2-1; ++j){   // 상단
        temp.push_back(board[r1-1][j]);
        board[r1-1][j] = temp[temp.size() - 2];
    }
    for(int i = r1-1; i < r2-1; ++i){   // 오른쪽
        temp.push_back(board[i][c2-1]);
        board[i][c2-1] = temp[temp.size() - 2];
    }
    for(int j = c2-1; j > c1-1; --j){   // 하단
        temp.push_back(board[r2-1][j]);
        board[r2-1][j] = temp[temp.size() - 2];
    }
    for(int i = r2-1; i > r1-1; --i){   // 왼쪽
        temp.push_back(board[i][c1-1]);
        board[i][c1-1] = temp[temp.size() - 2];        
    }
    board[r1-1][c1-1] = temp.back();
    temp.erase(temp.begin());
   
    return *min_element(temp.begin(), temp.end());
}

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    board = vector<vector<int>>(rows, vector<int>(columns));
    
    for(int i = 0; i < rows; ++i){
        for(int j = 0; j < columns; ++j){
            board[i][j] = i * columns + j + 1;
        }
    }
    for(auto q: queries){
        answer.push_back(rotate(q));
    }
    
    return answer;
}

효율성이 떨어져보여서 의심했는데 의외로 한 번에 통과함