πŸ… ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ 133500 : λ“±λŒ€ - Javascript

문제 μ„€λͺ…

인천 μ•žλ°”λ‹€μ—λŠ” 1λΆ€ν„° nκΉŒμ§€ μ„œλ‘œ λ‹€λ₯Έ λ²ˆν˜Έκ°€ 맀겨진 λ“±λŒ€ nκ°œκ°€ μ‘΄μž¬ν•©λ‹ˆλ‹€. λ“±λŒ€μ™€ λ“±λŒ€ 사이λ₯Ό μ˜€κ°€λŠ” 뱃길이 n-1개 μ‘΄μž¬ν•˜μ—¬, μ–΄λŠ λ“±λŒ€μ—μ„œ μΆœλ°œν•΄λ„ λ‹€λ₯Έ λͺ¨λ“  λ“±λŒ€κΉŒμ§€ 이동할 수 μžˆμŠ΅λ‹ˆλ‹€. λ“±λŒ€ κ΄€λ¦¬μž μœ€μ„±μ΄λŠ” μ „λ ₯을 아끼기 μœ„ν•˜μ—¬, 이 쀑 λͺ‡ 개의 λ“±λŒ€λ§Œ 켜 두렀고 ν•©λ‹ˆλ‹€. ν•˜μ§€λ§Œ λ“±λŒ€λ₯Ό μ•„λ¬΄λ ‡κ²Œλ‚˜ 꺼버리면, 뱃길을 μ˜€κ°€λŠ” 배듀이 μœ„ν—˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. ν•œ λ±ƒκΈΈμ˜ μ–‘μͺ½ 끝 λ“±λŒ€ 쀑 적어도 ν•˜λ‚˜λŠ” 켜져 μžˆλ„λ‘ λ“±λŒ€λ₯Ό 켜 두어야 ν•©λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄, μ•„λž˜ κ·Έλ¦Όκ³Ό 같이 λ“±λŒ€ 8κ°œμ™€ 7개의 뱃길듀이 μžˆλ‹€κ³  ν•©μ‹œλ‹€. 이 경우 1번 λ“±λŒ€μ™€ 5번 λ“±λŒ€ 두 개만 켜 두어도 λͺ¨λ“  뱃길은 μ–‘μͺ½ 끝 λ“±λŒ€ 쀑 ν•˜λ‚˜κ°€ 켜져 μžˆμœΌλ―€λ‘œ, 배듀은 μ•ˆμ „ν•˜κ²Œ μš΄ν•­ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

example img

λ“±λŒ€μ˜ 개수 nκ³Ό 각 뱃길이 μ—°κ²°λœ λ“±λŒ€μ˜ 번호λ₯Ό 담은 이차원 λ°°μ—΄ lighthouseκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§‘λ‹ˆλ‹€. μœ€μ„±μ΄κ°€ 켜 두어야 ν•˜λŠ” λ“±λŒ€ 개수의 μ΅œμ†Ÿκ°’μ„ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μž‘μ„±ν•΄μ£Όμ„Έμš”.


μ œν•œμ‚¬ν•­

  • 2 ≀ n ≀ 100,000
  • lighthouse의 길이 = n – 1
    • lighthouse λ°°μ—΄μ˜ 각 ν–‰ [a, b]λŠ” a번 λ“±λŒ€μ™€ b번 λ“±λŒ€κ°€ λ±ƒκΈΈλ‘œ μ—°κ²°λ˜μ–΄ μžˆλ‹€λŠ” μ˜λ―Έμž…λ‹ˆλ‹€.
      • 1 ≀ a β‰  b ≀ n
      • λͺ¨λ“  λ“±λŒ€λŠ” μ„œλ‘œ λ‹€λ₯Έ λ“±λŒ€λ‘œ 이동할 수 μžˆλŠ” 뱃길이 μ‘΄μž¬ν•˜λ„λ‘ μž…λ ₯이 μ£Όμ–΄μ§‘λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

n lighthouse result
8 [[1, 2], [1, 3], [1, 4], [1, 5], [5, 6], [5, 7], [5, 8]] 2
40 [[4, 1], [5, 1], [5, 6], [7, 6], [1, 2], [1, 3], [6, 8], [2, 9], [9, 10]] 3
  • 예제 #1
    λ³Έλ¬Έμ—μ„œ μ„€λͺ…ν•œ μ˜ˆμ‹œμž…λ‹ˆλ‹€.

  • 예제 #2
    뱃길은 μ•„λž˜ κ·Έλ¦Όκ³Ό 같이 μ—°κ²°λ˜μ–΄ μžˆμŠ΅λ‹ˆλ‹€. μœ€μ„±μ΄κ°€ 이쀑 1, 6, 9번 λ“±λŒ€ 3개만 켜 두어도 λͺ¨λ“  뱃길은 μ–‘μͺ½ 끝 λ“±λŒ€ 쀑 ν•˜λ‚˜κ°€ 켜져 있게 되고, μ΄λ•Œμ˜ λ“±λŒ€ 개수 3κ°œκ°€ μ΅œμ†Œκ°€ λ©λ‹ˆλ‹€. example img


풀이 κ³Όμ •

λ¨Όμ € 주어진 쑰건을 νŒŒμ•…ν•΄λ΄…μ‹œλ‹€.

  • 쑰건 1. lighthouse의 길이 = n – 1
    λ“±λŒ€ μ‚¬μ΄μ˜ 길의 μˆ˜κ°€ λ“±λŒ€μ˜ 수 -1μ΄λΌλŠ” 이 쑰건은 λ“±λŒ€μ˜ μˆ˜μ™€ 길의 μˆ˜κ°€ λ™μΌν•œ μ•„λž˜μ™€ 같은 ν˜•νƒœμ˜ 뱃길가 μ‘΄μž¬ν•˜μ§€ μ•ŠμŒμ„ μ•Œλ €μ€λ‹ˆλ‹€.

    description img

  • 쑰건 2. λͺ¨λ“  λ“±λŒ€λŠ” μ„œλ‘œ λ‹€λ₯Έ λ“±λŒ€λ‘œ 이동할 수 μžˆλŠ” 뱃길이 μ‘΄μž¬ν•˜λ„λ‘ μž…λ ₯이 μ£Όμ–΄μ§‘λ‹ˆλ‹€.
    λͺ¨λ“  λ“±λŒ€λŠ” λ‹€λ₯Έ λ“±λŒ€μ™€ 길이 μ—°κ²°λ˜μ–΄ μžˆλ‹€λΌλŠ” 이 쑰건은 μ•„λž˜μ™€ 같은 ν˜•νƒœμ˜ 뱃길이 μ‘΄μž¬ν•˜μ§€ μ•ŠμŒμ„ μ•Œλ €μ€λ‹ˆλ‹€.

    description img


μœ„ 두가지 쑰건을 톡해 λ±ƒκΈΈμ—λŠ” 항상 끝에 μœ„μΉ˜ν•œ λ“±λŒ€κ°€ μ‘΄μž¬ν•˜κ³ , λͺ¨λ“  λ“±λŒ€λŠ” 1개 μ΄μƒμ˜ κΈΈκ³Ό μ—°κ²°λ˜μ–΄μžˆμŒμ„ νŒŒμ•…ν–ˆμŠ΅λ‹ˆλ‹€.

이제 κ°€μž₯ 적은 수의 λ“±λŒ€λ§Œ 켜기 μœ„ν•΄ λ°˜λ“œμ‹œ μΌœμ Έμ•Όν•˜λŠ” λ“±λŒ€λ₯Ό μ°Ύμ•„μ•Όν•©λ‹ˆλ‹€.

λ¨Όμ € 끝에 μœ„μΉ˜ν•œ λ“±λŒ€, 즉, 길이 1개뿐인 λ“±λŒ€λŠ” λ°˜λ“œμ‹œ μžμ‹  ν˜Ήμ€ μ—°κ²°λœ λ“±λŒ€κ°€ μΌœμ Έμ•Όν•©λ‹ˆλ‹€. μ΄λ•Œ μžμ‹ μ„ μΌœλŠ” κ²½μš°μ—” 무쑰건 1개의 길만 λ°ν˜€μ§€μ§€λ§Œ μ—°κ²°λœ λ“±λŒ€μ˜ λΆˆλΉ›μ„ μΌ€ 경우 μ—¬λŸ¬κ°œμ˜ 길이 λ°ν˜€μ§ˆ 수 있기 λ•Œλ¬Έμ— μ—°κ²°λœ λ“±λŒ€μ˜ λΆˆλΉ›μ„ μΌœλ„λ‘ ν•©λ‹ˆλ‹€.

이 ν›„ λΆˆλΉ›μ˜ 영ν–₯을 λ°›μ•„ λΆˆλΉ›μ΄ ν•„μš” 없어진 λ“±λŒ€λ₯Ό λͺ©λ‘μ—μ„œ μ œκ±°ν•˜κ³  이 과정을 λ°˜λ³΅ν•΄ λ°˜λ“œμ‹œ λΆˆλΉ›μ΄ μΌœμ Έμ•Όν•˜λŠ” μ΅œμ†Œν•œμ˜ λ“±λŒ€μ˜ 수λ₯Ό ꡬ할 수 μžˆμŠ΅λ‹ˆλ‹€.


λ¨Όμ € λ“±λŒ€μ˜ 연결관계λ₯Ό κ΄€λ¦¬ν•˜κΈ° μœ„ν•΄ LightHouse 클래슀λ₯Ό μž‘μ„±ν–ˆμŠ΅λ‹ˆλ‹€. λ“±λŒ€ 번호λ₯Ό λ‹΄λŠ” id, μ—°κ²°λœ λ“±λŒ€ 객체λ₯Ό λ‹΄λŠ” connectsλ₯Ό 가진 ν΄λž˜μŠ€μž…λ‹ˆλ‹€. μ—°κ²°κ³Ό μ—°κ²° ν•΄μ œλ₯Ό μ²˜λ¦¬ν•˜λŠ” λ©”μ†Œλ“œκΉŒμ§€ λ¨Όμ € μž‘μ„±ν•΄λ‘κ² μŠ΅λ‹ˆλ‹€.

class Lighthouse {
  constructor(id) {
    this.id = id;
    this.connects = new Map();
  }

  //λ‹€λ₯Έ λ“±λŒ€μ™€ μ—°κ²°μ‹œν‚€λŠ” ν•¨μˆ˜
  //μžμ‹ κ³Ό λ‹€λ₯Έ λ“±λŒ€μ˜ μ—°κ²° λͺ©λ‘μ— μ„œλ‘œλ₯Ό 좔가함
  connect(target) {
    this.connects.set(target.id, target);
    target.connects.set(this.id, this);
  }

  //λ‹€λ₯Έ λ“±λŒ€μ™€ 연결을 ν•΄μ œμ‹œν‚€λŠ” ν•¨μˆ˜
  disconnect(target) {
    this.connects.delete(target.id);
    target.connects.delete(this.id);
  }
}

κ·Έ ν›„ solution ν•¨μˆ˜μ—μ„œ λͺ¨λ“  λ“±λŒ€μ˜ μ—°κ²° 관계λ₯Ό κΈ°λ‘ν•©λ‹ˆλ‹€. μ €λŠ” λ“±λŒ€ κ°μ²΄μ™€μ˜ ꡬ뢄을 μœ„ν•΄ solution ν•¨μˆ˜μ˜ 인자λ₯Ό lighthouse λŒ€μ‹  connects둜 λ³€κ²½ν–ˆμŠ΅λ‹ˆλ‹€.

function solution(n, connects) {
  //n개의 λ“±λŒ€ 객체가 λ‹΄κΈ΄ 2차원 λ°°μ—΄ 생성
  const lighthouses = new Map(
    [...Array(n).keys()].map((i) => [i + 1, new Lighthouse(i + 1)])
  );

  //λͺ¨λ“  λ“±λŒ€μ˜ μ—°κ²° 관계λ₯Ό 적용
  connects
    .map(([a, b]) => [lighthouses.get(a), lighthouses.get(b)])
    .forEach(([a, b]) => a.connect(b));

  return 0;
}

μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€μ˜ μˆ˜κ°€ 1κ°œμΈμ§€ 확인 ν•˜λŠ” λ©”μ†Œλ“œμ™€ μ œκ±°ν•  수 μžˆλŠ” λ“±λŒ€μ˜ λͺ©λ‘μ„ λ°˜ν™˜ν•˜λŠ” λ©”μ†Œλ“œλ₯Ό μž‘μ„±ν–ˆμŠ΅λ‹ˆλ‹€.

//μ—°κ²°λœ λ“±λŒ€μ˜ μˆ˜κ°€ 1κ°œμΈμ§€ ν™•μΈν•˜λŠ” ν•¨μˆ˜
//μ—°κ²°λœ λ“±λŒ€μ˜ μˆ˜κ°€ 1개인 경우 λ°˜λ“œμ‹œ μ—°κ²°λœ λ“±λŒ€μ˜ λΆˆλΉ›μ΄ μΌœμ Έμ•Όν•¨
hasOnlyOneConnect(){
  return this.connects.size === 1;
}

//μ œκ±°ν•  수 μžˆλŠ” λ“±λŒ€λ₯Ό λ°˜ν™˜ν•˜λŠ” ν•¨μˆ˜
//μ—°κ²°λœ λ“±λŒ€κ°€ 1개인 경우, μ—°κ²°λœ λ“±λŒ€μ˜ λͺ¨λ“  연결을 ν•΄μ œμ‹œν‚€κ³  λͺ¨λ“  연결이 ν•΄μ œλœ λ“±λŒ€μ˜ λͺ©λ‘λ₯Ό λ°˜ν™˜
getRemovalTargets(){
  //λͺ¨λ“  연결이 ν•΄μ œλ˜μ–΄ 제거될 λ“±λŒ€λ₯Ό λ‹΄λŠ” λ°°μ—΄
  //(== λΆˆλΉ›μ΄ 켜질 ν•„μš”κ°€ μ—†λŠ” λ“±λŒ€λ₯Ό λ‹΄λŠ” λ°°μ—΄)
  const removed = [];

  //μžμ‹ μ—κ²Œ μ—°κ²°λœ λ“±λŒ€κ°€ 1개인 경우
  if(this.hasOnlyOneConnect()){
    //μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€ (== λΆˆλΉ›μ΄ 켜질 λ“±λŒ€)
    const connect = this.connects.values().next().value;

    //μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€μ˜ λͺ¨λ“  연결을 ν•΄μ œμ‹œν‚€κ³ , λͺ¨λ“  연결이 ν•΄μ œλœ λ“±λŒ€λ₯Ό 제거 λͺ©λ‘μ— μΆ”κ°€
    //(== μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€μ˜ λΆˆλΉ›μ„ 켜고, λΆˆλΉ›μ΄ 켜질 ν•„μš”κ°€ μ—†λŠ” λ“±λŒ€λ₯Ό 제거 λͺ©λ‘μ— μΆ”κ°€)
    connect.connects.forEach(el => el.disconnect(connect) && removed.push(el));

    //μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€λ„ 제거 λͺ©λ‘μ— μΆ”κ°€
    //(== λΆˆλΉ›μ΄ μΌœμ§„ λ“±λŒ€λ„ 제거 λͺ©λ‘μ— μΆ”κ°€)
    removed.push(connect);
  }

  //μ œκ±°ν•  λ“±λŒ€ λͺ©λ‘μ„ 제거
  return removed;
}

λ§ˆμ§€λ§‰μœΌλ‘œ solution ν•¨μˆ˜μ—μ„œ λͺ¨λ“  길이 λ°ν˜€μ§ˆ λ•ŒκΉŒμ§€ λ°˜λ³΅ν•˜κ³  닡을 λ°˜ν™˜ν•˜λŠ” μ½”λ“œλ₯Ό μž‘μ„±ν•©λ‹ˆλ‹€.

let answer = 0;
//λͺ¨λ“  λ“±λŒ€κ°€ 제거될 λ•Œ κΉŒμ§€ 반볡
while (lighthouses.size > 0) {
  lighthouses.forEach((lighthouse) => {
    const targets = lighthouse.getRemovalTargets();
    if (targets.length) {
      //μ œκ±°ν•  λ“±λŒ€κ°€ μ‘΄μž¬ν•˜λŠ” 경우 (== λ“±λŒ€μ˜ λΆˆλΉ›μ΄ μΌœμ§„ 경우)
      //λΆˆλΉ›μ΄ μΌœμ§„ λ“±λŒ€μ˜ 수λ₯Ό μ¦κ°€μ‹œν‚€κ³  μ œκ±°ν•  λ“±λŒ€λ₯Ό lighthouseμ—μ„œ 제거
      answer++;
      targets.forEach((el) => lighthouses.delete(el.id));
    }
  });
}

//λΆˆλΉ›μ΄ μΌœμ§„ λ“±λŒ€μ˜ 수λ₯Ό λ°˜ν™˜
return answer;

μ΅œμ’… μ½”λ“œ

class Lighthouse {
  constructor(id) {
    this.id = id;
    this.connects = new Map();
  }

  //λ‹€λ₯Έ λ“±λŒ€μ™€ μ—°κ²°μ‹œν‚€λŠ” ν•¨μˆ˜ν•¨μˆ˜
  //본인과 λ‹€λ₯Έ λ“±λŒ€μ˜ μžμ‹μ— μ„œλ‘œλ₯Ό 좔가함
  connect(target) {
    this.connects.set(target.id, target);
    target.connects.set(this.id, this);
  }

  //λ‹€λ₯Έ λ“±λŒ€μ™€ 연결을 ν•΄μ œν•˜κ³ , λͺ¨λ“  연결이 ν•΄μ œλ˜μ—ˆλŠ” 지 μ—¬λΆ€λ₯Ό λ°˜ν™˜
  disconnect(target) {
    this.connects.delete(target.id);

    return this.connects.size === 0;
  }

  //μ—°κ²°λœ λ“±λŒ€μ˜ μˆ˜κ°€ 1κ°œμΈμ§€ ν™•μΈν•˜λŠ” ν•¨μˆ˜
  //μ—°κ²°λœ λ“±λŒ€μ˜ μˆ˜κ°€ 1개인 경우 λ°˜λ“œμ‹œ μ—°κ²°λœ λ“±λŒ€μ˜ λΆˆλΉ›μ΄ μΌœμ Έμ•Όν•¨
  hasOnlyOneConnect() {
    return this.connects.size === 1;
  }

  //μ œκ±°ν•  수 μžˆλŠ” λ“±λŒ€λ₯Ό λ°˜ν™˜ν•˜λŠ” ν•¨μˆ˜
  //μ—°κ²°λœ λ“±λŒ€κ°€ 1개인 경우, μ—°κ²°λœ λ“±λŒ€μ˜ λͺ¨λ“  연결을 ν•΄μ œμ‹œν‚€κ³  λͺ¨λ“  연결이 ν•΄μ œλœ λ“±λŒ€μ˜ λͺ©λ‘λ₯Ό λ°˜ν™˜
  getRemovalTargets() {
    //λͺ¨λ“  연결이 ν•΄μ œλ˜μ–΄ 제거될 λ“±λŒ€λ₯Ό λ‹΄λŠ” λ°°μ—΄
    //(== λΆˆλΉ›μ΄ 켜질 ν•„μš”κ°€ μ—†λŠ” λ“±λŒ€λ₯Ό λ‹΄λŠ” λ°°μ—΄)
    const removed = [];

    //μžμ‹ μ—κ²Œ μ—°κ²°λœ λ“±λŒ€κ°€ 1개인 경우
    if (this.hasOnlyOneConnect()) {
      //μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€ (== λΆˆλΉ›μ΄ 켜질 λ“±λŒ€)
      const connect = this.connects.values().next().value;

      //μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€μ˜ λͺ¨λ“  연결을 ν•΄μ œμ‹œν‚€κ³ , λͺ¨λ“  연결이 ν•΄μ œλœ λ“±λŒ€λ₯Ό 제거 λͺ©λ‘μ— μΆ”κ°€
      //(== μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€μ˜ λΆˆλΉ›μ„ 켜고, λΆˆλΉ›μ΄ 켜질 ν•„μš”κ°€ μ—†λŠ” λ“±λŒ€λ₯Ό 제거 λͺ©λ‘μ— μΆ”κ°€)
      connect.connects.forEach(
        (el) => el.disconnect(connect) && removed.push(el)
      );

      //μžμ‹ κ³Ό μ—°κ²°λœ λ“±λŒ€λ„ 제거 λͺ©λ‘μ— μΆ”κ°€
      //(== λΆˆλΉ›μ΄ μΌœμ§„ λ“±λŒ€λ„ 제거 λͺ©λ‘μ— μΆ”κ°€)
      removed.push(connect);
    }

    //μ œκ±°ν•  λ“±λŒ€ λͺ©λ‘μ„ 제거
    return removed;
  }
}

function solution(n, connects) {
  //n개의 λ“±λŒ€ 객체가 λ‹΄κΈ΄ 2차원 λ°°μ—΄ 생성
  const lighthouses = new Map(
    [...Array(n).keys()].map((i) => [i + 1, new Lighthouse(i + 1)])
  );

  //λͺ¨λ“  λ“±λŒ€μ˜ μ—°κ²° 관계λ₯Ό 적용
  connects
    .map(([a, b]) => [lighthouses.get(a), lighthouses.get(b)])
    .forEach(([a, b]) => a.connect(b));

  let answer = 0;
  //λͺ¨λ“  λ“±λŒ€κ°€ 제거될 λ•Œ κΉŒμ§€ 반볡
  while (lighthouses.size > 0) {
    lighthouses.forEach((lighthouse) => {
      const targets = lighthouse.getRemovalTargets();
      if (targets.length) {
        //μ œκ±°ν•  λ“±λŒ€κ°€ μ‘΄μž¬ν•˜λŠ” 경우 (== λ“±λŒ€μ˜ λΆˆλΉ›μ΄ μΌœμ§„ 경우)
        //λΆˆλΉ›μ΄ μΌœμ§„ λ“±λŒ€μ˜ 수λ₯Ό μ¦κ°€μ‹œν‚€κ³  μ œκ±°ν•  λ“±λŒ€λ₯Ό lighthouseμ—μ„œ 제거
        answer++;
        targets.forEach((el) => lighthouses.delete(el.id));
      }
    });
  }

  //λΆˆλΉ›μ΄ μΌœμ§„ λ“±λŒ€μ˜ 수λ₯Ό λ°˜ν™˜
  return answer;
}
  • TODO: μΆ”ν›„ μ½”λ“œμ™€ μ„€λͺ…을 λ‹€μ‹œ 정리할 μ˜ˆμ •μž…λ‹ˆλ‹€. μ½”λ“œλž‘ μ„€λͺ…이 λ„ˆλ¬΄ μž₯ν™©ν•˜κ²Œ μž‘μ„±λœ λŠλ‚Œμ΄ κ°•ν•΄μ„œβ€¦